peltorator

adamant hld

Jun 22nd, 2019
150
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. void dfs_sz(int v = 0) {
  2.     sz[v] = 1;
  3.     for(auto &u: g[v]) {
  4.         dfs_sz(u);
  5.         sz[v] += sz[u];
  6.         if(sz[u] > sz[g[v][0]]) {
  7.             swap(u, g[v][0]);
  8.         }
  9.     }
  10. }
  11.  
  12. void dfs_hld(int v = 0) {
  13.     in[v] = t++;
  14.     for(auto u: g[v]) {
  15.         nxt[u] = (u == g[v][0] ? nxt[v] : u);
  16.         dfs_hld(u);
  17.     }
  18.     out[v] = t;
  19. }
  20.  
  21.  
  22. https://codeforces.com/blog/entry/53170
RAW Paste Data