omggg's blog

By omggg, history, 19 months ago, In English

I am facing issues in questions in which Given is a tree with no fixed root, n<=1e5 . I can simply do the question if i traverse the tree for each node as root (n^2) but it gives TLE. I know i have to apply DP and rerooting concept.

Can anyone provide me a blog for this particular topic? Or some handful questions on that to learn with the topic? (my rating:1600)

Any help is appreciated. Thanks

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Subtree can be specified not by a (root; subtree root) pair (there are $$$O(n^2)$$$ of them), but by (subtree root; edge to subtree's parent, possibly none) pair. And there are only $$$O(n)$$$ of them.

So instead of calculating parent[v] and running dfs(int v), you can run dfs(int v, int parent = -1) and cache all results for a specific vertex in a hash map.

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, I know one such question involving the re-rooting concept. https://codeforces.com/contest/1092/problem/F

I hope it helps!

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Tutorial : https://codeforces.com/blog/entry/68139 Problem : https://codeforces.com/contest/1187/problem/E Read it's official editorial too.

It's not that hard concept.

»
19 months ago, # |
  Vote: I like it +5 Vote: I do not like it

This comment has problems that can be solved using rerooting idea comment