fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  3. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  4. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  5. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  6. #define ll int
  7. #define el "\n"
  8. #define fi first
  9. #define se second
  10. #define _ROOT_ int main()
  11. #define M 1000000007
  12. #define MAXN 100002
  13. #define LOG 19
  14. #define Bit(i) (1LL << i )
  15. #define INF (1ll<<30)
  16. #define NAME "file"
  17. #define BLOCK 500
  18. #define debug(a) cout << #a << " = " << a << endl;
  19. using namespace std;
  20.  
  21. ll n, m, q;
  22. ll total_sum;
  23. ll high[MAXN] ;
  24. ll dist[MAXN] ;
  25. ll d[MAXN ] ;
  26. ll st[MAXN], fin[MAXN], timeDfs ;
  27. ll num_color[MAXN ] ;
  28. ll curC ;
  29.  
  30. ll mu[MAXN];
  31. bool prime[MAXN];
  32. vector<ll> primes;
  33.  
  34. vector<pair<ll, ll>> adj[MAXN ] ;
  35. vector<ll> red , cur ;
  36. ll euler[2 * MAXN];
  37. ll first_pos[MAXN];
  38. ll euler_cnt;
  39. ll lg2[2 * MAXN];
  40. pair<ll, ll> rmq[2 * MAXN][LOG + 1];
  41.  
  42.  
  43. void dfs(ll u, ll p) {
  44.     st[u] = ++ timeDfs ;
  45.         euler[++euler_cnt] = u;
  46.     first_pos[u] = euler_cnt;
  47.  
  48.     for(auto [v, weight] : adj[u]) if(v != p ) {
  49.             high[v] = high[u] + 1 ;
  50.             dist[v] = dist[u] + weight;
  51.             dfs(v, u  ) ;
  52.             euler[++euler_cnt] = u;
  53.         }
  54.     fin[u] = timeDfs;
  55. }
  56.  
  57. void bfs() {
  58.     for(ll v : red )cur.push_back(v) ;
  59.     FOR(i, 1, n ) d[i] = INF ;
  60.     red.clear() ; 
  61.     queue<ll> q ;
  62.     for(ll v : cur ) d[v] = 0, q.push(v) ;
  63.     red.clear() ;
  64.     while(!q.empty() ) {
  65.         ll u = q.front() ;
  66.         q.pop() ;
  67.         for(auto [v , w ] : adj[u]) if(d[v] == INF ) {
  68.                 d[v] = d[u] + 1 ;
  69.                 q.push(v) ;
  70.             }
  71.     }
  72.  
  73. }
  74.  
  75. void init_lca() {
  76.     FOR(i, 1, euler_cnt) {
  77.         rmq[i][0] = {high[euler[i]], euler[i]};
  78.     }
  79.     lg2[1] = 0;
  80.     FOR(i, 2, euler_cnt) lg2[i] = lg2[i / 2] + 1;
  81.  
  82.     FOR(j, 1, LOG) {
  83.         for (ll i = 1; i + (1 << j) - 1 <= euler_cnt; i++) {
  84.             rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
  85.         }
  86.     }
  87. }
  88.  
  89. ll LCA(ll u, ll v ) {
  90.     ll l = first_pos[u];
  91.     ll r = first_pos[v];
  92.     if (l > r) swap(l, r);
  93.     ll k = lg2[r - l + 1];
  94.     return min(rmq[l][k], rmq[r - (1 << k) + 1][k]).second;
  95. }
  96.  
  97. ll LEN(ll a, ll b ) {
  98.     return dist[a] + dist[b] - 2 * dist[LCA(a, b ) ] ;
  99. }
  100.  
  101.  
  102.  
  103.  
  104. void init() {
  105.     cin >> n >> q ;
  106.     FOR(i, 2, n ) {
  107.         ll x, y, w  = 1;
  108.         cin >> x >> y  ;
  109.         adj[x].push_back({y, w}) ;
  110.         adj[y].push_back({x, w}) ;
  111.     }
  112. }
  113.  
  114. void solve() {
  115.     high[1] = 0;
  116.     dfs(1, 1 ) ;
  117.     init_lca();
  118.     red.push_back(1) ;
  119.     bfs() ;
  120.     FOR(cnt, 1, q ) {
  121.         ll t, u  ;
  122.         cin >> t >> u ;
  123.         if(t == 2 ) {
  124.         ll ans = d[u] ;
  125.         for(ll v : red ) ans = min(ans , LEN(u , v )) ;
  126. //        for(ll v : red ) {
  127. //                debug(u) ;
  128. //        debug(v) ;
  129. //            debug(LEN(u , v )) ;
  130. //        }
  131.  
  132.         cout << ans << el ;
  133.         } else {
  134.             red.push_back(u) ;
  135.             if(red.size() > BLOCK ) bfs() ;
  136.         }
  137.     }
  138. }
  139.  
  140. _ROOT_ {
  141.     // freopen(NAME".inp" , "r" , stdin);
  142.     // freopen(NAME".out" , "w", stdout) ;
  143.     ios_base::sync_with_stdio(0);
  144.     cin.tie(0);
  145.     cout.tie(0);
  146.     int t = 1; // cin >> t ;
  147.     while(t--) {
  148.         init();
  149.         solve();
  150.     }
  151.     return (0&0);
  152. }
  153.  
Success #stdin #stdout 0s 7660KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/CNCegr
language:
C++14 (gcc 8.3)
created:
1 day 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!