Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- void dfs_sz(int u = 0)
- {
- sz[u] = 1;
- for (auto &v : graph[u])
- {
- dfs_sz(v);
- sz[u] += sz[v];
- if (sz[v] > sz[ graph[u][0] ])
- swap(v, graph[u][0]);
- }
- }
- void dfs_hld(int u = 0)
- {
- in[u] = t++;
- rin[ in[u] ] = u;
- for (auto v : graph[u])
- {
- nxt[v] = (v == g[u][0] ? nxt[u] : v);
- dfs_hld(v);
- }
- out[u] = t;
- }
- 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.
- Sample Problem:
- Codechef - Persistent oak
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement