fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define el '\n'
  4. #define fi first
  5. #define sec second
  6. #define pb push_back
  7. #define int long long
  8. #define pii pair<int,int>
  9. #define sz(v) (int)(v).size()
  10. #define all(v) (v).begin(),(v).end()
  11. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
  12. #define REP(i, a, b) for(int i = (a), _b = (b); i >= _b; i--)
  13.  
  14. using namespace std;
  15.  
  16. const int INF = (int)1e18 + 462010;
  17. const int MAX_N = 1e5;
  18. const int LOG = 17;
  19.  
  20. vector<int> g[MAX_N + 5];
  21. int best[MAX_N + 5];
  22. int n, q;
  23.  
  24. namespace Centroid_Decomposition{
  25.     int dist[LOG + 5][MAX_N + 5], lv[MAX_N + 5];
  26.     int sub[MAX_N + 5], par[MAX_N + 5];
  27.     vector<int> adj[MAX_N + 5];
  28.     bool removed[MAX_N + 5];
  29.     int root;
  30.  
  31.     void dfs_sz(int u, int dad){
  32.         sub[u] = 1;
  33.         for(int v : g[u]) if(v != dad && !removed[v]){
  34.             dfs_sz(v, u);
  35.             sub[u] += sub[v];
  36.         }
  37.     }
  38.  
  39.     int find_centroid(int u, int dad, int total){
  40.         for(int v : g[u]) if(v != dad && !removed[v] && sub[v] > total / 2){
  41.             return find_centroid(v, u, total);
  42.         }
  43.         return u;
  44.     }
  45.  
  46.     void dfs_dist(int u, int dad, int level, int d){
  47.         dist[level][u] = d;
  48.         for(int v : g[u]) if(v != dad && !removed[v]){
  49.             dfs_dist(v, u, level, d + 1);
  50.         }
  51.     }
  52.  
  53.     void build_centroid(int u, int pre, int level){
  54.         dfs_sz(u, 0);
  55.         int centroid = find_centroid(u, 0, sub[u]);
  56.  
  57.         if(!root) root = centroid;
  58.         removed[centroid] = true;
  59.         lv[centroid] = level;
  60.  
  61.         dfs_dist(centroid, 0, level, 0);
  62.  
  63.         if(pre != -1){
  64.             adj[pre].pb(centroid);
  65.             par[centroid] = pre;
  66.         }
  67.  
  68.         for(int v : g[centroid]) if(!removed[v]){
  69.             build_centroid(v, centroid, level + 1);
  70.         }
  71.     }
  72.  
  73.     void paint(int u){
  74.         for(int v = u; v != 0; v = par[v]){
  75.             best[v] = min(best[v], dist[lv[v]][u]);
  76.         }
  77.     }
  78.  
  79.     int query(int u){
  80.         int res = INF;
  81.         for(int v = u; v != 0; v = par[v]){
  82.             res = min(res, best[v] + dist[lv[v]][u]);
  83.         }
  84.         return res;
  85.     }
  86. } using namespace Centroid_Decomposition;
  87.  
  88. void Input(){
  89.     cin >> n >> q;
  90.     FOR(i, 1, n - 1){
  91.         int u, v;
  92.         cin >> u >> v;
  93.  
  94.         g[u].pb(v);
  95.         g[v].pb(u);
  96.     }
  97. }
  98.  
  99. void Prepare(){
  100.     build_centroid(1, -1, 0);
  101.     FOR(u, 1, n) best[u] = INF;
  102. }
  103.  
  104. void Solve(){
  105.     paint(1);
  106.     while(q--){
  107.         int type, x;
  108.         cin >> type >> x;
  109.  
  110.         if(type == 1) paint(x);
  111.         else cout << query(x) << el;
  112.     }
  113. }
  114.  
  115. signed main(){
  116.     ios_base::sync_with_stdio(0);
  117.     cin.tie(0);
  118.  
  119.     Input();
  120.     Prepare();
  121.     Solve();
  122.  
  123.     return 0;
  124. }
  125.  
Success #stdin #stdout 0.01s 12092KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7TAHr2
language:
C++ (gcc 8.3)
created:
4 hours 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!