Halo,

Story: Its 4AM here and i cant sleep so i brought you a nice trick and couple of problems to practice it.

Introduction

(Our dp changes if we change root of the tree, otherwise it wont make any sens to use this trick)

Lets say we want to find $$$dp_v$$$ for every vertex in a tree, this dp must be updated using the children of vertex $$$v$$$. Then the trick allows you to move the root from a vertex to one of it's adjacent vertices in $$$O(1)$$$.

It will be much better if the problem wants you to move the root to all vertices and find maximum of dp-s or etc.

Implementation

First calculate dp for a root $$$rat$$$. Its obvious that if we change root $$$r$$$ to one of its adjacent vertex $$$v$$$, then only $$$dp_r$$$ and $$$dp_v$$$ can change, so that we can update $$$dp_r$$$ using its new children and past $$$dp_r$$$, also $$$dp_v$$$ can be updated the same way.

Note: Don't iterate over $$$r$$$ and $$$v$$$ children, it will be $$$O(\sum\limits_v\binom{d_v}{2})$$$ if you do it and $$$W(n^2)$$$ so just don't.($$$d_v$$$ is the degree of vertex $$$v$$$

Now being able to move the root with distance one, we will run a dfs from $$$rat$$$, and move the root with dfs.

See the semi-code below, i hope it helps for better understanding:

void dfs(int nw){
      int fixDPnow = dp[nw], fixDPv;
      for(v in *children* of nw){//we mean the exact children of nw if we hang the tree from rat
            fixDPv = dp[v];
            move(v);//it will move the root to v and update dp
            dfs(v);
            //following two lines will move back the root to nw and update the dp
            dp[v] = fixDPv;
            dp[nw] = fixDPnow;
      }
}

int main(){
      calculateDP(rat);//it will calculate the DP when it's root is rat
      dfs(rat);//this will calculate move the root to all the vertices
}

Applications

Problem1 Solution

Problem2//i cant open atcoder =(.

Problem3 Solution//this solution will be updated to highlight the trick

Problem4//again i cant see the problem but i believe i have solved it.

Problem5//no solution right now

Probelm6//no solution right now

Please comment the problems which can be solved using this trick.

Thanks for your attention.