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

• +6

| Write comment?
 » 4 years ago, # |   0 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.
•  » » 4 years ago, # ^ |   +18 As commented here: https://codeforces.com/blog/entry/73110?#comment-573669 your solution is quadratic (or rather sum of squares of degrees).
•  » » » 4 years ago, # ^ |   +8 Good point, thank you. Not all solutions like this are quadratic, though, depends on how one recalculates.
•  » » 4 years ago, # ^ |   0 Thenks yeputons. Was looking for something like this only
 » 4 years ago, # |   0
•  » » 4 years ago, # ^ |   0 THanks :)
 » 4 years ago, # |   0 Hi, I know one such question involving the re-rooting concept. https://codeforces.com/contest/1092/problem/FI hope it helps!
•  » » 4 years ago, # ^ |   0 THenks
 » 4 years ago, # |   0
 » 4 years ago, # |   +5 This comment has problems that can be solved using rerooting idea comment
•  » » 4 years ago, # ^ |   0 Thanks Pavan :)