fork download
copy 
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <ctime>
  4. #include <cmath>
  5. #include <cstring>
  6.  
  7. #include <iostream>
  8. #include <algorithm>
  9. #include <string>
  10. #include <vector>
  11. #include <set>
  12. #include <map>
  13. #include <queue>
  14.  
  15. #pragma comment(linker, "/STACK:65536000")
  16.  
  17. using namespace std;
  18.  
  19. typedef long long ll;
  20. typedef unsigned long long ull;
  21. typedef unsigned int uint;
  22.  
  23. struct edge
  24. {
  25. 	int u, v;
  26. 	edge() { u = v = 0; }
  27. 	edge(int _u, int _v) { u = _u; v = _v; }
  28. };
  29.  
  30. edge e[100100];
  31. vector<int> all[100100];
  32. vector<int> tree[100100];
  33. int root, d[100100], tp[100100], pt, etp[100100], ed[100100], n, m;
  34.  
  35. void dfs(int x, int par)
  36. {
  37. 	tp[x] = pt;
  38. 	if (all[x].size() == 1) tree[pt].resize(d[x]);
  39. 	for (int i = 0; i < all[x].size(); i++)
  40. 	{
  41. 		if (all[x][i] == par) continue;
  42. 		d[all[x][i]] = d[x] + 1;
  43. 		dfs(all[x][i], x);
  44. 	}
  45. }
  46.  
  47. void add(int x, int y, int v)
  48. {
  49. 	for (int i = y; i < tree[x].size(); i = (i | (i + 1)))
  50. 		tree[x][i] += v;
  51. }
  52.  
  53. int get(int x, int y)
  54. {
  55. 	int ans = 0;
  56. 	for (int i = y - 1; i >= 0; i = (i & (i + 1)) - 1)
  57. 		ans += tree[x][i];
  58. 	return ans;
  59. }
  60.  
  61. int main()
  62. {
  63. 	scanf("%d", &n);
  64. 	for (int i = 0; i < n - 1; i++)
  65. 	{
  66. 		int u, v;
  67. 		scanf("%d%d", &u, &v); u--; v--;
  68. 		e[i] = edge(u, v); all[u].push_back(v); all[v].push_back(u);
  69. 	}
  70. 	root = 0;
  71. 	for (int i = 0; i < n; i++)
  72. 		if (all[i].size() > all[root].size()) root = i;
  73. 	for (int i = 0; i < all[root].size(); i++)
  74. 	{
  75. 		pt = i;
  76. 		d[all[root][i]] = 1;
  77. 		dfs(all[root][i], root);
  78. 	}
  79. 	for (int i = 0; i < n - 1; i++)
  80. 	{
  81. 		if (e[i].u == root) etp[i] = tp[e[i].v], ed[i] = 0;
  82. 		else if (e[i].v == root) etp[i] = tp[e[i].u], ed[i] = 0;
  83. 		else etp[i] = tp[e[i].u], ed[i] = min(d[e[i].u], d[e[i].v]);
  84. 	}
  85. 	scanf("%d", &m);
  86. 	for (int i = 0; i < m; i++)
  87. 	{
  88. 		int t, u, v;
  89. 		scanf("%d%d", &t, &u);
  90. 		if (t == 3)
  91. 		{
  92. 			scanf("%d", &v); u--; v--;
  93. 			int x = get(tp[u], d[u]), y = get(tp[v], d[v]);
  94. 			if (tp[u] == tp[v])
  95. 			{
  96. 				if (x == y) printf("%d\n", abs(d[u] - d[v]));
  97. 				else printf("-1\n");
  98. 			}
  99. 			else
  100. 			{
  101. 				if (x + y == 0) printf("%d\n", d[u] + d[v]);
  102. 				else printf("-1\n");
  103. 			}
  104. 		}
  105. 		else
  106. 		{
  107. 			u--;
  108. 			if (t == 1) add(etp[u], ed[u], -1);
  109. 			else add(etp[u], ed[u], 1);
  110. 		}
  111. 	}
  112. 	return 0;
  113. }
Success #stdin #stdout 0s 7928KB
comments (?)
stdin
copy 
7
1 5
6 4
2 3
3 5
5 6
3 7
1
3 4 2
stdout
copy 
4
https://ideone.com/7sgTFP
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!