Advertisement
dipBRUR

Easiest HLD on subtree

Oct 4th, 2018
170
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.77 KB | None | 0 0
  1. void dfs_sz(int u = 0)
  2. {
  3.     sz[u] = 1;
  4.     for (auto &v : graph[u])
  5.     {
  6.         dfs_sz(v);
  7.         sz[u] += sz[v];
  8.         if (sz[v] > sz[ graph[u][0] ])
  9.             swap(v, graph[u][0]);
  10.     }
  11. }
  12.  
  13. void dfs_hld(int u = 0)
  14. {
  15.     in[u] = t++;
  16.     rin[ in[u] ] = u;
  17.     for (auto v : graph[u])
  18.     {
  19.         nxt[v] = (v == g[u][0] ? nxt[u] : v);
  20.         dfs_hld(v);
  21.     }
  22.     out[u] = t;
  23. }
  24.  
  25. Then you will have such array that subtree of u corresponds to segment [in[u];out[u]) and the path from u to the last vertex in ascending heavy path from u (which is nxt[u]) will be [in[ nxt[u] ]; in[u]] subsegment which gives you the opportunity to process queries on paths and subtrees simultaneously in the same segment tree.
  26. Sample Problem:
  27. Codechef - Persistent oak
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement