### omggg's blog

By omggg, history, 4 years ago, 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 #dp, Comments (11)
| Write comment?
 » 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
 »
•  » » THanks :)
 » Hi, I know one such question involving the re-rooting concept. https://codeforces.com/contest/1092/problem/FI hope it helps!
•  » » THenks
 »
 » This comment has problems that can be solved using rerooting idea comment
•  » » Thanks Pavan :)