关于换根dp

看到网上的方法多多少少比较复杂，所以决定写一下。

首先对于一道换根dp题应该是先要会不换根版本的。

然后可以按照欧拉序（括号序）换根。对于欧拉序中相邻的两个节点必有一条边把它们相连，所以换根的时候只需要从新统计 $1$ 个子树的信息。

觉得自己的语言表达能力太烂，还是上题目比较好。

[P3478 [POI2008] STA-Station](https://www.luogu.com.cn/problem/P3478)

求一个点的应该很好做，考虑 $f_u$ 表示点 $u$ 的子树中的答案，$sz_u$ 为 $u$的子树大小，有转移方程：
$$f_u=\sum_{v \in ch}(f_v+sz_v)$$

考虑如何进行换根。


假如把 $v$ 换成新的根，结果如下


可以发现，只有 $rt$ 与 $v$ 的信息改变了，所以将 $rt$ 减去 $v$ 的贡献，$v$
加上 $rt$ 的贡献即可。

code:

#include<vector>
#include<iostream>
using namespace std;

#define ll long long

const int MX=2e6+7;

vector<int > g[MX];
ll sz[MX],f[MX],ans=0;
int n,x,y,pos=0;

int read(){
    int x=0,ch=getchar();
    while(!(ch>=48&&ch<=57))ch=getchar();
    while(ch>=48&&ch<=57)x=x*10+ch-48,ch=getchar();
    return x;
}

void write(int x){
    if(x>9)write(x/10);
    putchar(x%10+48);
}

void dp(int x,int fa){
    sz[x]=f[x]=0;
    for(int i=0;i<g[x].size();i++){
        int to=g[x][i];
        if(to==fa)continue;
        dp(to,x);
        sz[x]+=sz[to];
        f[x]+=f[to]+sz[to];
    }
    sz[x]++;
}

void chg_rt(int rt,int newrt){
    f[rt]-=f[newrt]+sz[newrt];
    sz[rt]-=sz[newrt];
    f[newrt]+=f[rt]+sz[rt];
    sz[newrt]+=sz[rt];
    if(f[newrt]>ans){
        ans=f[newrt];
        pos=newrt;
    }
}

void dfs(int x,int fa){
    for(int i=0;i<g[x].size();i++){
        int to=g[x][i];
        if(to==fa)continue;
        chg_rt(x,to);
        dfs(to,x);
        chg_rt(to,x);
    }
}

int main(){
    ios::sync_with_stdio(false);
    n=read();
    for(int i=1;i<n;i++){
        x=read();
        y=read();
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dp(1,1);
    dfs(1,1);
    write(pos);
    return 0;
}

[CF708C Centroids](https://codeforces.com/problemset/problem/708/C)

直接换根dp，不写了。