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[0]=mp(-1,0);
dp[edge[0][0]]=mp(-1,0);
cout<<solve(edge[0][0],edge[0][0]).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)?
Please explain how to re-root the tree in this question??
https://atcoder.jp/contests/abc160/submissions/11326156 I've solved it now. To reroot the tree quickly, you have to undo the effect of the other node. It may look horrifyingly ugly, and that's because it is, but it's easy to understand. Firstly, the size will change. so we undo the last *fact[size] in the dp, subtract the subtree of the other node, and multiply by fact[newsize]. Then we undo the dp, by multiplying by its modular inverse, and then multiplying by the fact[size of it's subtree]. Then we have completely undone the other node. Now put the dp relation in the other node, just like how we did it normally. only thing is since the subtree size has increased, we have to undo the last *fact[size] and multiply by its new subtree size.
Can you elaborate rerooting for sample test case 4 here
Test Case 4
I explained a bit about how to do rerooting in this problem here: https://codeforces.com/blog/entry/75262#comment-594874
Can you give the test case where I am getting Wrong Answer! my submission link is:- Atcoder submisssion link and what changes shall I adopt to convert it to full AC. Thanks in advance !