fork download
copy 
  1. //Created By Mayur Agarwal :)
  2.  
  3. #include <iostream>
  4. #include <stdio.h>
  5. #include <cmath>
  6. #include <vector>
  7. #include <string>
  8. #include <cstring>
  9. #include <set>
  10. #include <algorithm>
  11. #include <map>
  12. #include <iterator>
  13. #include <functional>
  14. #include <queue>
  15.  
  16. #define ll long long
  17. #define ind(a) scanf("%d",&a)
  18. #define in(a) scanf("%lld",&a)
  19. #define inc(a) scanf("%c",&a)
  20. #define ins(a) scanf("%s",a)
  21. #define pr(a) printf("%lld\n",a)
  22. #define debug(x) cout << #x << " = " << x << endl
  23. #define MS0(X) memset((X), 0, sizeof((X)))
  24. #define MS1(X) memset((X), -1, sizeof((X)))
  25. #define pb push_back
  26. #define ff first
  27. #define ss second
  28. #define SIZE 100010
  29. const int mod = 10000007;
  30.  
  31. using namespace std;
  32. typedef pair<int, int>pll;
  33. int dp[19][(1 << 19)], h[SIZE], sz[SIZE], par[SIZE];
  34. set<int>S[SIZE];
  35.  
  36. /*Using centroid Decomposition of a tree */
  37.  
  38.  
  39. /*----------- Pre-Processing ------------*/
  40. inline void dfs(int v = 0, int p = -1)
  41. {
  42. 	if (~p)
  43. 		h[v] = h[p] + 1;
  44. 	dp[0][v] = p;
  45. 	for (int i = 1; i <= 18; i++)
  46. 	{
  47. 		if (~dp[i - 1][v])
  48. 			dp[i][v] = dp[i - 1][dp[i - 1][v]];
  49. 	}
  50. 	for (auto it = S[v].begin(); it != S[v].end(); it++)
  51. 	{
  52. 		int u = *it;
  53. 		if (u != p)
  54. 			dfs(u, v);
  55. 	}
  56. }
  57. inline int lca(int v, int u)
  58. {
  59. 	if (h[v] < h[u])
  60. 		swap(v, u);
  61.  
  62. 	for (int i = 18; i >= 0; --i)
  63. 	{
  64. 		if (~dp[i][v] && h[dp[i][v]] >= h[u])
  65. 			v = dp[i][v];
  66. 	}
  67. 	if (v == u)
  68. 		return v;
  69. 	for (int i = 18; i >= 0; --i)
  70. 	{
  71. 		if (dp[i][v] - dp[i][u])
  72. 		{
  73. 			v = dp[i][v];
  74. 			u = dp[i][u];
  75. 		}
  76. 	}
  77. 	return dp[0][v];
  78. }
  79. inline int dist(int v, int u)
  80. {
  81. 	return h[v] + h[u] - 2 * h[lca(v, u)];
  82. }
  83.  
  84.  
  85. /*-----------------Decomposition part--------------------------*/
  86. int nn;
  87. inline void dfs1(int v, int p)
  88. {
  89. 	nn++;
  90. 	sz[v] = 1;
  91. 	for (auto it = S[v].begin(); it != S[v].end(); it++)
  92. 	{
  93. 		int u = *it;
  94. 		if (u != p)
  95. 		{
  96. 			dfs1(u, v);
  97. 			sz[v] += sz[u];
  98. 		}
  99. 	}
  100. }
  101.  
  102. inline int dfs2(int v, int p)
  103. {
  104. 	for (auto it = S[v].begin(); it != S[v].end(); it++)
  105. 	{
  106. 		int u = *it;
  107. 		if (u != p && sz[u] > nn / 2)
  108. 		{
  109. 			return dfs2(u, v);
  110. 		}
  111. 	}
  112. 	return v;
  113. }
  114.  
  115. inline void decompose(int v = 0, int p = -1)
  116. {
  117. 	nn = 0;
  118. 	dfs1(v, v);
  119. 	int centroid = dfs2(v, v);
  120. 	if (p == -1)
  121. 		p = centroid;
  122. 	par[centroid] = p;
  123. 	for (auto it = S[centroid].begin(); it != S[centroid].end(); it++)
  124. 	{
  125. 		int u = *it;
  126. 		S[u].erase(centroid);
  127. 		decompose(u, centroid);
  128. 	}
  129. 	S[centroid].clear();
  130. }
  131.  
  132.  
  133.  
  134. /*----------------- Handle the Queries -----------------*/
  135.  
  136. set<pll>q[SIZE];
  137. set<pll>::iterator iter;
  138. bool white[SIZE];
  139. inline void update(int u)
  140. {
  141. 	int x = u;
  142. 	while (1)
  143. 	{
  144. 		q[x].insert(pll(u, dist(x, u)));
  145. 		if (x == par[x])
  146. 			break;
  147. 		x = par[x];
  148. 	}
  149. }
  150.  
  151. inline int distW(int x)
  152. {
  153. 	while (!q[x].empty())
  154. 	{
  155. 		iter = q[x].begin();
  156. 		if (!white[(*iter).ff])
  157. 			q[x].erase(q[x].begin());
  158. 		else
  159. 		{
  160. 			return (*iter).ss;
  161. 		}
  162. 	}
  163. 	return mod;
  164. }
  165.  
  166. inline int query(int u)
  167. {
  168. 	int x = u;
  169. 	int res = mod;
  170. 	while (1)
  171. 	{
  172. 		res = min(res, distW(x) + dist(u, x));
  173. 		if (x == par[x])
  174. 			break;
  175. 		x = par[x];
  176. 	}
  177. 	return res;
  178. }
  179.  
  180.  
  181. int main()
  182. {
  183. #ifndef ONLINE_JUDGE
  184. 	freopen("input.txt", "r", stdin);
  185. #endif
  186. 	ios_base::sync_with_stdio(0); cin.tie(0);
  187. 	int n;
  188. 	cin >> n;
  189. 	for (int i = 1; i < n; i++)
  190. 	{
  191. 		int u, v;
  192. 		cin >> u >> v;
  193. 		u--;
  194. 		v--;
  195. 		S[u].insert(v);
  196. 		S[v].insert(u);
  197. 	}
  198. 	dfs();
  199. 	decompose();
  200. 	int q;
  201. 	cin >> q;
  202. 	while (q--)
  203. 	{
  204. 		int typ, v;
  205. 		cin >> typ >> v;
  206. 		v--;
  207. 		if (typ == 0)
  208. 		{
  209. 			if (white[v])
  210. 			{
  211. 				white[v] = 0;
  212. 			}
  213. 			else
  214. 			{
  215. 				white[v] = 1;
  216. 			}
  217.  
  218. 			if (white[v])
  219. 				update(v);
  220. 		}
  221. 		else
  222. 		{
  223. 			int res = query(v);
  224. 			if (res >= mod)
  225. 			{
  226. 				cout << "-1\n";
  227. 			}
  228. 			else
  229. 			{
  230. 				cout << res << endl;
  231. 			}
  232. 		}
  233. 	}
  234. 	return 0;
  235. }
Success #stdin #stdout 0s 48328KB
comments (?)
stdin
copy 
10
1 2
1 3
2 4
1 5
1 6
4 7
7 8
5 9
1 10
10
0 6
0 6
0 6
1 3
0 1
0 1
1 3
1 10
1 4
1 6
stdout
copy 
2
2
2
3
0
https://ideone.com/bEIMe1
language:
C++14 (gcc 8.3)
created:
8 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!