fork download 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. // - Bài này ta sẽ áp dụng kiến thức liên quan đến prefix sum
  12. // - Gọi sum(u) = tổng của cây con gốc u = tổng các phần tử trong đoạn a[tin(u), tout(u)]
  13. // => Khi ta update giá trị a(u) của 1 đỉnh u nào đấy thì sum(anc) với anc là tổ tiên của u cũng sẽ thay đổi theo, 
  14. //    hay nói cách khác là sum(anc) của các đỉnh anc nằm trên đường đi từ 1 đến u đều sẽ bị thay đổi.
  15. // => Để update một đường đi (u, v) lên thêm val đơn vị, ta làm như sau:
  16. // 1. a(u) += val, a(v) += val
  17. // 2. a(lca(u, v)) -= val
  18. // 3. a(up[0][lca(u, v)]) -= val (với lca(u, v) != 1)
  19. // - Sau cùng ta có sum(u) chính là giá trị của đỉnh u ở thời điểm sau khi update
  20. // - Lưu ý cách update trên chỉ áp dụng với trường hợp trọng số của đỉnh, với trường hợp trọng số của cạnh thì cần chỉnh sửa lại một chút.
  21.  
  22. const int N = 2e5 + 5;  
  23. const int LOG = 18;   
  24.  
  25. int n, q; 
  26. vector<int> adj[N]; 
  27.  
  28. int up[LOG][N]; 
  29. int tin[N], tout[N], timer; 
  30.  
  31. void dfs1(int u, int p) {
  32. 	tin[u] = ++timer;  
  33. 	up[0][u] = p; 
  34. 	for (int i = 1; i < LOG; i++) {
  35. 		up[i][u] = up[i - 1][up[i - 1][u]];  
  36. 	}
  37. 	for (int v : adj[u]) {
  38. 		if (v == p) continue; 
  39. 		dfs1(v, u); 
  40. 	}
  41. 	tout[u] = timer;
  42. }
  43.  
  44. bool isAncestor(int u, int v) {
  45. 	return (tin[u] <= tin[v] && tout[v] <= tout[u]); 
  46. }
  47.  
  48. int lca(int u, int v) {
  49. 	if (isAncestor(u, v)) return u;  
  50. 	if (isAncestor(v, u)) return v;   
  51. 	for (int i = LOG - 1; i >= 0; i--) {
  52. 		if (!isAncestor(up[i][u], v)) {
  53. 			u = up[i][u]; 
  54. 		}
  55. 	}
  56. 	return up[0][u]; 
  57. }
  58.  
  59. int sum[N]; 
  60.  
  61. void dfs2(int u, int p) {
  62. 	for (int v : adj[u]) {
  63. 		if (v == p) continue;  
  64. 		dfs2(v, u); 
  65. 		sum[u] += sum[v]; 
  66. 	}
  67. }
  68.  
  69. int main() {
  70. 	ios::sync_with_stdio(false); 
  71. 	cin.tie(nullptr); 	
  72. 	cin >> n >> q;  
  73. 	for (int i = 0; i < n - 1; i++) {
  74. 		int u, v; 
  75. 		cin >> u >> v; 
  76. 		adj[u].push_back(v); 
  77. 		adj[v].push_back(u); 
  78. 	}
  79.  
  80. 	timer = 0;  
  81. 	dfs1(1, 1); 
  82.  
  83. 	for (int i = 0; i < q; i++) {
  84. 		int u, v; 
  85. 		cin >> u >> v;  
  86. 		int lca_uv = lca(u, v); 
  87. 		sum[u]++, sum[v]++; 
  88. 		sum[lca_uv]--; 
  89. 		if (lca_uv != 1) sum[up[0][lca_uv]]--; 
  90. 	}
  91.  
  92. 	dfs2(1, 1); 
  93.  
  94. 	for (int u = 1; u <= n; u++) {
  95. 		cout << sum[u] << ' ';
  96. 	}
  97. }
Success #stdin #stdout 0.01s 24684KB
comments (?)
stdin 
5 3
1 2
1 3
3 4
3 5
1 3
2 5
1 4
stdout 
3 1 3 1 1
https://ideone.com/914uJr
language:
C++14 (gcc 8.3)
created:
173 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!