Hi, Its 4AM here and i cant sleep so i brought you a nice trick and couple of problems to practice the trick.

Introduction

(Our dp change 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$$$(probable the trick still works if we can update $$$dp_v$$$ from its parent), and it works in $$$O(t)$$$ to calculate it. Also this trick will be meaning full if we want to calculate $$$val_r$$$ for every $$$r$$$, $$$val_r$$$ is equal to $$$dp_r$$$ when $$$r$$$ is the root of the tree(i hope you understand what i said). Say that the dp works in $$$O(T)$$$ time, then the trick allows you to calculate $$$val_r$$$ in $$$O(T+n)$$$.

Implementation

First calculate dp for a random 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 also $$$dp_v$$$ can be updated the same way. Now being able to move the root with distance one, we will run a dfs from $$$rat$$$, and move the root with dfs and store $$$val_v$$$, i hope the last part wasn't as bad as i think is, my poor English don't allow me to right it in words, so i right it in codes :).

See the semi-code below :

void dfs(int now){
      val[now] = dp[now];
      int fixDPnow = dp[now], fixDPv;
      for(v in *children* of now){//we mean the exact children of now if we root the tree from rat(sorry for poor English)
            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 now and update the dp
            dp[v] = fixDPv;
            dp[now] = fixDPnow;
      }
}

int main(){
      calculateDP(rat);//it will calculate the DP when it's root is rat
      dfs(rat);//this will calculate val[v] for all v
}

Applications