fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // why am I so weak
  5.  
  6. int n, m, k;
  7.  
  8. #define MAX_LOG 17
  9.  
  10. int par[MAX_LOG][100055];
  11.  
  12. struct edge {int to; int id;};
  13.  
  14. vector<edge> g[100055];
  15.  
  16. int depth[100055];
  17. int d[100055];
  18.  
  19. int dfn[100055], t;
  20.  
  21. vector<int> vg[100055];
  22.  
  23. void dfs(int v, int par = -1, int d = 0) {
  24. 	depth[v] = d;
  25. 	::par[0][v] = par;
  26.  
  27. 	dfn[v] = t++;
  28.  
  29. 	for (auto e : g[v]) if (e.to != par) {
  30. 		dfs(e.to, v, d + 1);
  31. 	}
  32. }
  33. int lca(int u, int v) {
  34. 	if (depth[u] > depth[v]) swap(u, v);
  35.  
  36. 	for (int i = 0; i < MAX_LOG; i++) {
  37. 		if (((depth[v] - depth[u]) >> i) & 1) {
  38. 			v = par[i][v];
  39. 		}
  40. 	}
  41.  
  42. 	if (u == v) return u;
  43.  
  44. 	for (int i = MAX_LOG - 1; i >= 0; i--) {
  45. 		if (par[i][u] != par[i][v]) {
  46. 			u = par[i][u];
  47. 			v = par[i][v];
  48. 		}
  49. 	}
  50.  
  51. 	return par[0][v];
  52. }
  53. void rdfs(int v, int par, vector<int> &res) {
  54. 	for (auto e : g[v]) if (e.to != par) {
  55. 		rdfs(e.to, v, res);
  56.  
  57. 		if (d[e.to] >= k) {
  58. 			res.push_back(e.id);
  59. 		}
  60.  
  61. 		d[v] += d[e.to];
  62. 	}
  63. }
  64. void gao(int v) {
  65. 	for (auto u : vg[v]) {
  66. 		d[u]++;
  67. 		d[v]--;
  68. 		gao(u);
  69. 	}
  70. }
  71. int main() {
  72. 	scanf("%d %d %d", &n, &m, &k);
  73.  
  74. 	for (int i = 0; i + 1 < n; i++) {
  75. 		int x, y;
  76. 		scanf("%d %d", &x, &y);
  77. 		x--, y--;
  78.  
  79. 		g[x].push_back((edge){y, i});
  80. 		g[y].push_back((edge){x, i});
  81. 	}
  82.  
  83. 	dfs(0);
  84.  
  85. 	for (int i = 0; i + 1 < MAX_LOG; i++) for (int j = 0; j < n; j++) {
  86. 		if (~par[i][j]) par[i + 1][j] = par[i][par[i][j]];
  87. 		else par[i + 1][j] = -1;
  88. 	}
  89.  
  90. 	while (m--) {
  91. 		int x;
  92. 		scanf("%d", &x);
  93.  
  94. 		vector<int> vec(x);
  95.  
  96. 		for (int i = 0; i < x; i++) {
  97. 			scanf("%d", &vec[i]);
  98. 			vec[i]--;
  99.  
  100. 			vg[vec[i]].clear();
  101. 		}
  102.  
  103. 		sort(vec.begin(), vec.end(), [&] (int u, int v) {
  104. 			return dfn[u] < dfn[v];
  105. 		});
  106.  
  107. 		vec.erase(unique(vec.begin(), vec.end()), vec.end());
  108.  
  109. 		x = (int)vec.size();
  110.  
  111. 		for (int i = 0; i + 1 < x; i++) {
  112. 			vec.push_back(lca(vec[i], vec[i + 1]));
  113. 		}
  114.  
  115. 		sort(vec.begin(), vec.end(), [&] (int u, int v) {
  116. 			return dfn[u] < dfn[v];
  117. 		});
  118.  
  119. 		vec.erase(unique(vec.begin(), vec.end()), vec.end());
  120.  
  121. 		for (auto u : vec) vg[u].clear();
  122.  
  123. 		static int sta[100055];
  124. 		int size = 0;
  125.  
  126. 		sta[size++] = vec[0];
  127.  
  128. 		for (int i = 1; i < (int)vec.size(); i++) {
  129. 			int u = vec[i];
  130. 			int l = lca(u, sta[size - 1]);
  131.  
  132. 			if (l != sta[size - 1]) {
  133. 				while (size >= 2 && depth[sta[size - 2]] >= depth[l]) {
  134. 					vg[sta[size - 2]].push_back(sta[size - 1]);
  135. 					size--;
  136. 				}
  137.  
  138. 				if (sta[size - 1] != l) {
  139. 					vg[l].push_back(sta[--size]);
  140. 					sta[size++] = l;
  141. 				}
  142. 			}
  143.  
  144. 			sta[size++] = u;
  145. 		}
  146.  
  147. 		for (int i = 0; i + 1 < size; i++) vg[sta[i]].push_back(sta[i + 1]);
  148.  
  149. 		gao(vec[0]);
  150. 	}
  151.  
  152. 	vector<int> res;
  153.  
  154. 	rdfs(0, -1, res);
  155.  
  156. 	sort(res.begin(), res.end());
  157.  
  158. 	printf("%d\n", (int)res.size());
  159.  
  160. 	for (int i = 0; i < (int)res.size(); i++) {
  161. 		if (i) printf(" ");
  162. 		printf("%d", res[i] + 1);
  163. 	}
  164.  
  165. 	puts("");
  166.  
  167. 	return 0;
  168. }
  169.  
  170.  
Success #stdin #stdout 0s 28968KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/fFIXFT
language:
C++14 (gcc 8.3)
created:
7 years 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!