Halo :D!

Story: It was 4AM and i was unable to 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
}

Problems

I cant open some sites so there is no solution for them, sorry.

You can read the same technique here, also the site has some problems.

Problem1 Solution

Problem2

Problem3 Solution

Problem4

Problem5//no solution right now

Probelm6//no solution right now

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

Advanced

Lets say that the problem has queries, such that each query gives two vertices $$$r$$$ and $$$v$$$ and wants you to calculate $$$f(r, v)$$$, its equal to $$$dp_v$$$ when the root is $$$r$$$. It can be solved with rerooting + ancestors binary lifting, it will answers each query in $$$O(Q*log_2n)$$$ time($$$O(log_2n)$$$ for binary lifting), and also $$$O(n*log_2n)$$$ precalculation.

So lets see how it works, for every edge($$$v \to u$$$) find $$$dp_v$$$ if the root is $$$u$$$ and $$$dp_u$$$ if the root is $$$v$$$, it will take the time it takes to move the root around and an additional $$$O(n)$$$ memory. Then if the query is in form $$$v$$$ and $$$v$$$(i.e. it wants to find $$$dp_v$$$ such that the tree is rooted at vertex $$$v$$$ itself) then the answer will be $$$n$$$, otherwise the problem is reduced to the following problem:

You are given two vertices $$$r$$$ and $$$u$$$$$$(u \ne r)$$$ what is the second vertex in the unique path from $$$u$$$ to $$$r$$$(it means we want to find out which child of $$$u$$$ is the closest to $$$r$$$).

This problem can be solved using binary lifting, if $$$u$$$ is not an ancestor of $$$r$$$, then the answer is $$$u$$$'s parent(the root is vertex 1), otherwise move $$$r$$$ using binary lifting until it's depth is equal to $$$u$$$'s depth plus 1, it can be done in $$$O(log_2n)$$$, let the answer to the reduced problem be $$$z$$$, then the answer to the whole query is equal to $$$f(z, u)$$$ such that $$$z$$$ is adjacent to $$$v$$$, we have precalculated this value so just print it :).

See the semi-code below, i skipped known parts so i will use $$$moveto(u)$$$ to move the root to vertex $$$u$$$, $$$f(r, u)$$$ for $$$dp_u$$$ when the root is $$$r$$$ and $$$rise(r, u)$$$ to find the ancestor of $$$r$$$ with depth equal to $$$depth_u+1$$$ in $$$O(log_2n)$$$.

void dfs(int nw, int pr){
      store dp[nw] for answer of f(nw, nw);
      par[nw] = pr;
      int fdpnw = dp[nw], fdpu;
      for(u in exact children of nw){//skip u == pr
            fdpu = dp[u];
            moveto(u);//moving root to u
            store dp[nw] for answer of f(u, nw);
            dfs(u, nw);//calculate the data for all vertices in the subtree of u
            moveto(nw);//moving root to nw
      }
}

int main(){
      calculateDP(1);//calculates DP when root is 1
      par[1] = 1;
      dfs(1, 1);//it will move the root to all the vertices and calculates the data needed.
      int q;
      cin >> q;
      while(q--){
            int r, u;
            cin >> r >> u;
            if(r == u){
                  cout << n << '\n';
                  continue;
            }
            if(u is not an ancestor of r){
                  cout << f(par[u], u) << '\n'; //using the calculated data
                  continue;
            }
            
            r = rise(r, u);//its O(log_2n)
            cout << f(r, u) << '\n'; //again using the calculated data
      }
}

I tried to add a problem from polygon for the advanced part, the problem is completed but i couldn't bring it to codeforces, so you cant submit your code, but i give you the link for problem's package, it includes 50 tests, validator and checker, main correct solution and problem statement, you can try running them in polygon.Windows Package(50 MB) Linux Package(45 MB)

In the problem mentioned above $$$dp_u$$$ is the size of the subtree of $$$u$$$, so solution will be like this :

#include <bits/stdc++.h>
#define fr first
#define sc second

using namespace std;
const int MN = 2e5+7;

int dp[MN], dep[MN], timer, l, n, ans[MN], tin[MN], tout[MN];
vector<int> g[MN];
map<pair<int, int>, int> data;
vector<vector<int>> up;

bool is_ancestor(int u, int v){
    return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}

int rise(int u, int v){
    if(dep[u] == dep[v]+1)return u;
    int ln = dep[u] - dep[v] - 1;
    int c = 0;
    while(ln){
        if(ln & 1)u = up[u][c];
        ln >>= 1;
        c++;
    }
    return u;
}

void cal(int nw, int pr){
    dp[nw] = 1;
    for(auto u : g[nw]){
        if(u == pr)continue;
        cal(u, nw);
        dp[nw] += dp[u];
    }
}

void store(int r, int u, int vl){
    data[{r, u}] = vl;
}

void dfs(int nw, int pr){
    int v = nw;

    tin[v] = ++timer;
    up[v][0] = pr;
    for (int i = 1; (1 << i) <= dep[v]; ++i)
        up[v][i] = up[up[v][i-1]][i-1];

    for(auto u : g[nw]){
        if(u == pr)continue;
        dep[u] = dep[nw]+1;
        int fdpnw = dp[nw], fdpu = dp[u];

        store(nw, u, dp[u]);

        dp[nw] -= dp[u];
        dp[u] += dp[nw];

        store(u, nw, dp[nw]);
        dfs(u, nw);

        dp[nw] = fdpnw;
        dp[u] = fdpu;
    }

    tout[nw] = ++timer;
}

void preprocess(int root) {
    l = ceil(log2(n));
    up.assign(n, vector<int>(l + 1));
    dfs(root, root);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int q;
    cin >> n >> q;
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cal(0, 0);
    for(int i = 0; i < n; i++)ans[i] = dp[i];
    preprocess(0);

    while(q--){
        int u, r;
        cin >> r >> u;
        r--; u--;
        if(r == u){
            cout << n << '\n';
            continue;
        }
        if(is_ancestor(u, r)){
            r = rise(r, u);
            cout << data[{r, u}] << '\n';
        }
        else{
            cout << ans[u] << '\n';
        }
    }
}

I used maps to store dp, so the solution is a little slower than expected. The solution is checked using stresses tab in polygon.

I hope it will help you with solving DP-Tree problems.

Thanks for your attention.