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 runningdfs(int v), you can rundfs(int v, int parent = -1)and cache all results for a specific vertex in a hash map.As commented here: https://mirror.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://mirror.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 :)