fork download
  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
stdin
7
1 5
6 4
2 3
3 5
5 6
3 7
1
3 4 2
stdout
4