Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Everule's blog

Help needed in rerooting trees, Atcoder beginner contest problem F
By Everule, 5 years ago, In English

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)?

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please explain how to re-root the tree in this question??

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I explained a bit about how to do rerooting in this problem here: https://mirror.codeforces.com/blog/entry/75262#comment-594874

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 !

    → Reply