fork(1) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gZ85l8
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

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!