https://atcoder.jp/contests/abc160/tasks/abc160_f //Question link
https://atcoder.jp/contests/abc160/submissions/11324766 //My TLE submission
I need help in understanding how to reroot the tree in O(n) I think I have understood how to reroot the tree but I cannot understand how to do it for every node. For example
dp.resize(n,mp(-1,0)); //dp[u]=(the actual answer, size of subtree) cout<<solve(0,0).first<<"\n"; dp=mp(-1,0); dp[edge]=mp(-1,0); cout<<solve(edge,edge).first<<"\n";
The following code seems to correctly calculate the answer for the root node and it's first edge. But how do I reroot the tree in such a way that it goes to all edges and calculates the answer in O(n)?