omggg's blog

Re-rooting Tree DP?
By omggg, history, 4 years 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

Comments Comments (11)
| Write comment?
»
4 years 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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

May be this one can help.

→ Reply
»
4 years 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!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

1324F - Maximum White Subtree

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply