fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. using std::sort;
  5. using std::pair;
  6. using std::swap;
  7. using std::max;
  8. using std::make_pair;
  9. const int INF = 0x3f3f3f3f;
  10. const int maxn = 300000 + 200;
  11. const int maxe = maxn * 2;
  12. #define x first
  13. #define y second
  14. struct Edge {
  15.     int edge;
  16.     int head[maxn], to[maxe], next[maxe];
  17.     Edge() {
  18.         edge = 0;
  19.         memset(head, -1, sizeof head);
  20.     }
  21.     void addedge(int u, int v) {
  22.         to[edge] = v;
  23.         next[edge] = head[u];
  24.         head[u] = edge++;
  25.     }
  26. } E;
  27. int n, dep[maxn], anc[maxn][20], size[maxn];
  28.  
  29. int dfn[maxn], dfs_clock = 0;
  30. void dfs(int x) {
  31. 	size[x] = 1;
  32. 	dfn[x] = ++dfs_clock;
  33. 	for(int i = E.head[x]; i != -1; i =E.next[i]) {
  34. 		if(E.to[i] != anc[x][0]) {
  35. 			anc[E.to[i]][0] = x;
  36. 			dep[E.to[i]] = dep[x] + 1;
  37. 			for(int j = 1; j <= 19; ++j) {
  38. 				anc[E.to[i]][j] = anc[anc[E.to[i]][j - 1]][j - 1];
  39. 			}
  40. 			dfs(E.to[i]);
  41. 			size[x] += size[E.to[i]];
  42. 		}
  43. 	}
  44. }
  45. bool cmp(int x, int y) {
  46. 	return dfn[x] < dfn[y];
  47. }
  48. int get(int u, int d) {
  49. 	for(int i = 19; 0 <= i; --i) {
  50. 		if(dep[anc[u][i]] >= d) {
  51. 			u = anc[u][i];
  52. 		}
  53. 	}
  54. 	return u;
  55. }
  56. int lca(int x, int y) {
  57. 	if(dep[x] < dep[y]) {
  58. 		swap(x, y);
  59. 	}
  60. 	for(int i = 19; 0 <= i; --i) {
  61. 		if(dep[anc[x][i]] >= dep[y]) {
  62. 			x = anc[x][i];
  63. 		}
  64. 	}
  65. 	if(x == y) return x;
  66. 	for(int i = 19; 0 <= i; --i) {
  67. 		if(anc[x][i] != anc[y][i]) {
  68. 			x = anc[x][i];
  69. 			y = anc[y][i];
  70. 		}
  71. 	}
  72. 	return anc[x][0];
  73. }
  74.  
  75. int fa[maxn], h[maxn], m, tot, ans[maxn], rec[maxn], w[maxn], t[maxn], val[maxn], stack[maxn];
  76. pair<int, int> g[maxn];
  77. void solve() {
  78. 	scanf("%d", &m);
  79. 	tot = m;
  80. 	for(int i = 1; i <= m; ++i) {
  81. 		scanf("%d", &h[i]);
  82. 		t[i] = rec[i] = h[i];
  83. 		g[h[i]] = make_pair(0, h[i]);
  84. 		ans[h[i]] = 0;
  85. 	}
  86. 	sort(h + 1, h + m + 1, cmp);
  87. 	for(int top = 0, i = 1; i <= m; ++i) {
  88. 		if(!top) {
  89. 			stack[++top] = h[i];
  90. 			fa[h[i]] = 0;
  91. 		} else {
  92. 			int u = h[i], p = lca(u, stack[top]);
  93. 			for(; dep[stack[top]] > dep[p] && 0 < top; --top) {
  94. 				if(dep[stack[top - 1]] <= dep[p]) {
  95. 					fa[stack[top]] = p;
  96. 				}
  97. 			}
  98. 			if(stack[top] != p) {
  99. 				fa[p] = stack[top];
  100. 				stack[++top] = p;
  101. 				t[++tot] = p;
  102. 				g[p] = make_pair(INF, 0);
  103. 			}
  104. 			fa[u] = p;
  105. 			stack[++top] = u;
  106. 		}
  107. 	}
  108. 	sort(t + 1, t + tot + 1, cmp);			
  109. 	for(int i = 1; i <= tot; ++i) {
  110. 		int p = t[i];
  111. 		val[p] = size[p];
  112. 		if(i != 1) {
  113. 			w[p] = dep[p] - dep[fa[p]];
  114. 		}
  115. 	}
  116. 	for(int i = tot; 1 < i; --i) {
  117. 		int u = t[i], p = fa[u];
  118. 		g[p] = min(g[p], make_pair(g[u].x + w[u], g[u].y));
  119. 	}
  120. 	for(int i = 2; i <= tot; ++i) {
  121. 		int u = t[i], p = fa[u];
  122. 		g[u] = min(g[u], make_pair(g[p].x + w[u], g[p].y));
  123. 	}
  124. 	for(int i = 1; i <= tot; ++i) {
  125. 		int u = t[i], p = fa[u];
  126. 		if(i == 1) {
  127. 			ans[g[u].y] = n - size[u];
  128. 		} else {
  129. 			int x = get(u, dep[p] + 1), sum = size[x] - size[u];
  130. 			val[p] -= size[x];
  131. 			if(g[p].y == g[u].y) {
  132. 				ans[g[u].y] += sum;
  133. 			} else {
  134. 				int mid = dep[u] - ((g[p].x + g[u].x + w[u]) / 2 - g[u].first);
  135. 				if((g[p].x + g[u].x + w[u]) % 2 == 0 && g[u].y > g[p].y) {
  136. 					++mid;
  137. 				}
  138. 				int y = size[get(u, mid)] - size[u];
  139. 				ans[g[u].second] += y;
  140. 				ans[g[p].second] += sum - y;
  141. 			}
  142. 		}
  143. 	}
  144. 	for(int i = 1; i <= tot; ++i) {
  145. 		ans[g[t[i]].second] += val[t[i]];
  146. 	}
  147. 	for(int i = 1; i <= m; ++i) {
  148. 		printf("%d ", ans[rec[i]]);
  149. 	}
  150. 	puts("");
  151. }
  152.  
  153. int main() {
  154. 	scanf("%d", &n);
  155. 	for(int i = 1; i < n; ++i) {
  156. 		int u, v;
  157. 		scanf("%d%d", &u, &v);
  158. 		E.addedge(u, v);
  159. 		E.addedge(v, u);
  160. 	}
  161. 	dep[1] = 1;
  162. 	dfs(1);
  163. 	int test_case;
  164. 	for(scanf("%d", &test_case); test_case; --test_case) {
  165. 		solve();
  166. 	}
  167.  
  168. 	return 0;
  169. }
Success #stdin #stdout 0s 47912KB
comments (?)
stdin
copy 
10            
2 1           
3 2            
4 3          
5 4           
6 1            
7 3            
8 3            
9 4            
10 1          
5             
2             
6 1            
5
2 7 3 6 9
1             
8             
4             
8 7 10 3
5
2 9 3 5 8
stdout
copy 
1 9 
3 1 4 1 1 
10 
1 1 3 5 
4 1 3 1 1
https://ideone.com/SzDy91
HNOI2014 世界树 worldtree
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

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!