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

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.As commented here: https://codeforces.com/blog/entry/73110?#comment-573669 your solution is quadratic (or rather sum of squares of degrees).

Good point, thank you. Not all solutions like this are quadratic, though, depends on how one recalculates.

Thenks yeputons. Was looking for something like this only

May be this one can help.

THanks :)

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

I hope it helps!

THenks

1324F - Maximum White Subtree

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

Thanks Pavan :)