fork(1) download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. const int MAX = 1e5 + 5;
  6. const int LOG = 18;
  7. const int INF = 1e6;
  8. template<int MAXN, int MAXLG> struct centroidDecomp{
  9. vector<int> adj[MAXN];
  10. int sz[MAXN]; //size of subtree
  11. int cpar[MAXN];//parent in centroid tree
  12. multiset<pair<int, int>> cdist[MAXN];
  13. int color [MAX];
  14. bool vis[MAXN]; //visited array
  15.  
  16. int L[MAXLG][MAXN]; //lca
  17. int depth[MAXN]; //depth
  18. void addEdge(int u, int v){
  19. adj[u].emplace_back(v);
  20. adj[v].emplace_back(u);
  21. }
  22. int getDist(int v){
  23. if(cdist[v].empty() == true){
  24. return INF;
  25. }
  26. return (*(cdist[v].rbegin())).first;
  27. }
  28. void dfs(int n, int p) {
  29. depth[n] = depth[p] + 1;
  30. L[0][n] = p;
  31. for (int i = 0; i < MAXLG - 1; i++)
  32. L[i + 1][n] = L[i][L[i][n]];
  33. for (int v : adj[n]) if (v != p) {
  34. dfs(v, n);
  35. }
  36. }
  37.  
  38. int lca(int u, int v) {
  39. if (depth[u] < depth[v])
  40. swap(u, v);
  41. for (int i = MAXLG - 1; i >= 0; i--) {
  42. if (depth[u] - (1<<i) >= depth[v])
  43. u = L[i][u];
  44. }
  45. for (int i = MAXLG - 1; i >= 0; i--) {
  46. if (L[i][u] != L[i][v])
  47. u = L[i][u], v = L[i][v];
  48. }
  49. return u == v ? u : L[0][u];
  50. }
  51.  
  52. int dist(int u, int v) {
  53. return depth[u] + depth[v] - 2 * depth[lca(u, v)];
  54. }
  55.  
  56. void dfs_sz(int n, int p=-1) {
  57. sz[n] = 1;
  58. for (int v : adj[n]) if (v != p && !vis[v]) {
  59. dfs_sz(v, n);
  60. sz[n] += sz[v];
  61. }
  62. }
  63.  
  64. int centroid(int n) {
  65. dfs_sz(n);
  66. int num = sz[n];
  67. int p = -1;
  68. do {
  69. int nxt = -1;
  70. for (int v : adj[n]) if (!vis[v] && v != p) {
  71. if (2 * sz[v] > num)
  72. nxt = v;
  73. }
  74. p = n, n = nxt;
  75. } while (~n);
  76. return p;
  77. }
  78. int closest(int v){
  79. int ans = getDist(v);
  80. // cout << ans << " asdf "<< v << endl;
  81. for (int n = v; n>=0; n = cpar[n]){
  82. ans = min(ans, getDist(n) + dist(n, v));
  83. //cout << getDist(n) << "asdf" << endl;
  84. }
  85. return ans;
  86. }
  87. void toggle(int v){
  88. color[v] = 1-color[v];
  89. if(color[v] == 1){
  90. for (int n = v; n>=0; n = cpar[n]){
  91. cdist[n].insert(make_pair(dist(n, v), v));
  92. //cout << dist(n, v) << " inserted " << v << " " << n << endl;
  93. }
  94. }
  95. else{
  96. for (int n = v; n>=0; n = cpar[n]){
  97. cdist[n].erase(make_pair(dist(n, v), v));
  98. }
  99. }
  100.  
  101. }
  102. void centroid_decomp(int n, int p=-1) {
  103. int c = centroid(n);
  104. vis[c] = true;
  105. cpar[c] = p;
  106. for (int v : adj[c]) if (!vis[v]) {
  107. centroid_decomp(v, c);
  108. }
  109. }
  110. };
  111.  
  112. int n, q;
  113.  
  114. centroidDecomp<MAX, LOG> cd;
  115. int main() {
  116. ios_base::sync_with_stdio(false);
  117. cin.tie(0);
  118. cin >> n;
  119. for (int i = 0; i < n-1; i++) {
  120. int u, v;
  121. cin >> u >> v;
  122. u--; v--;
  123. cd.addEdge(u, v);
  124. }
  125.  
  126. cd.dfs(0, 0);
  127. cd.centroid_decomp(0);
  128. cin >> q;
  129. for(int i = 0; i<q; i++) {
  130. int t, v;
  131. cin >> t >> v;
  132. v--;
  133. if (t == 0) {
  134. cd.toggle(v);
  135. }
  136. else {
  137. int ans = cd.closest(v);
  138. if(ans >= n || ans <0){
  139. cout << -1 << endl;
  140. continue;
  141. }
  142. cout << ans << endl;;
  143. }
  144. }
  145. return 0;
  146. }
  147.  
Success #stdin #stdout 0s 30968KB
stdin
Standard input is empty
stdout
Standard output is empty