换根DP

复习或者学习可以参考以下两篇文章：

【朝夕的ACM笔记】动态规划-换根DP - 知乎 (zhihu.com)

[学习笔记]换根dp - 洛谷专栏 (luogu.com)

下面是对应的一些练习题目：（题单链接）

换根DP - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

---

有一些题实在是太板子了，所以我就没怎么写注释了。

P3478 [POI2008] STA-Station - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e6+10;
const int INF=0x3f3f3f3f;
const int mod=19650827;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
ll dp[MAXN];
ll size[MAXN];
ll depth[MAXN];
//遇到换根dp了 学习一下
//关键是有两个dfs
//dfs1负责统计每个节点u距离根节点1的深度 以及以u为根的子树的大小
//dfs2负责计算dp数组  dp[u]表示以u为根节点的深度和
//状态转移方程就是
//dp[v]=g[v]+(dp[u]-(g[v]+size[v]))+(size[1]-size[v])
//g[u] 表示子树里所有节点到u的深度和
//size[u] 表示的是以u为根节点的子树大小
//depth[u]表示从u到1的深度(以后有用)
//v是u的子节点
//那么当根从u->v时 我们就要更新dp数组 dp[v]=g[v]+dp[u]-(g[v]+size[v])+(size[1]-size[v])
//显然的 g[v]需要加上去 而原来的dp[u]就要减去v子树里的信息
//一开始我也认为为什么是减去g[v]+size[v] 而不是减去g[v]
//我们可以这样想 u是v的父节点 那么v的子树里的所有点到u的距离都要额外+1 全部的额外和就是size[v]
//总共算出来就是g[v]+size[v]
//后面的减去size[1]-size[v]也是依此类推
//其实化简后就可以发现是dp[to]=dp[x]-2*size[to]+size[1];
//根本用不到g数组
//原题中没有确定根节点 那么我们不妨假设根节点是1 需要预处理出dp[1]
//先dfs1 预处里出depth数组 全部累加就可以得到dp[1]
//后面dfs2就是正规的状态转移了

//还有一个小细节 注意得开long long 
//因为可能在计算的过程中溢出了 虽然数据范围1e6乍一看人畜无害的样子
//这个细节一定要留意
struct Edge
{
    int from,to;
};
std::vector<Edge> edge[MAXN];;
void dfs1(int x,int fa)
{
    size[x]=1;
    for(auto t:edge[x])
    {
        int to=t.to;
        if(to==fa)  continue;
        depth[to]=depth[x]+1;
        dfs1(to,x);
        size[x]+=size[to];
    }
}
void dfs2(int x,int fa)
{
    for(auto t:edge[x])
    {
        int to=t.to;
        if(to==fa)  continue;
        dp[to]=dp[x]-2*size[to]+size[1];
        dfs2(to,x);
    }
}
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v;    std::cin>>u>>v;
        edge[u].push_back({u,v});
        edge[v].push_back({v,u});
    }
    dfs1(1,-1);
    for(int i=1;i<=n;i++)   dp[1]+=depth[i];
    dfs2(1,-1);
    ll ans=0;
    int pos=0;
    for(int i=1;i<=n;i++)
    {
        if(dp[i]>ans)
        {
            ans=dp[i];
            pos=i;
        }
    }
    std::cout<<pos;
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

[ABC348E] Minimize Sum of Distances - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=19650827;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
ll dp[MAXN];
ll size[MAXN];
ll depth[MAXN];
ll a[MAXN];
struct Edge
{
    int from,to;
};
std::vector<Edge> edge[MAXN];;
void dfs1(int x,int fa)
{
    size[x]=a[x];
    for(auto t:edge[x])
    {
        int to=t.to;
        if(to==fa)  continue;
        depth[to]=depth[x]+1;
        dfs1(to,x);
        size[x]+=size[to];
    }
}
void dfs2(int x,int fa)
{
    for(auto t:edge[x])
    {
        int to=t.to;
        if(to==fa)  continue;
        dp[to]=dp[x]-(2*size[to]-size[1]);
        dfs2(to,x);
    }
}
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v;    std::cin>>u>>v;
        edge[u].push_back({u,v});
        edge[v].push_back({v,u});
    }
    for(int i=1;i<=n;i++)   std::cin>>a[i];
    dfs1(1,-1);
    for(int i=1;i<=n;i++)   dp[1]+=depth[i]*a[i];
    dfs2(1,-1);
    ll ans=LONG_LONG_MAX;
    for(int i=1;i<=n;i++)
    {
        ans=std::min(ans,dp[i]);
    }
    std::cout<<ans;
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

Tree Painting - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=2e5+10;
const int INF=0x3f3f3f3f;
const int mod=19650827;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
ll dp[MAXN];
ll size[MAXN];
ll depth[MAXN];
ll a[MAXN];
//这道题题意看上去很难 其实是绕 关键是弄清楚要求什么就好了
//题目要求的是数量的贡献值 所以不需要求边长
//题目要求进行n次操作 其实答案只跟第一次操作 也就是将哪个点染为黑色有关
//wsm？
//一个点的贡献来源于以它为根的子树和它的祖先中能达到的白点数。
//当这个点的父亲已被染成黑色，该点的祖先颜色已无法对该点贡献造成影响，只与子树有关，而子树不受顺序影响。

//其实预处理都是一样的
//dp[i] 表示以i为根节点的答案
//不妨还是以1为根开始预处理
//这里dp[1]+=size[i]
//其中size[i]表示的是以i为根的子树的大小
//显然的 以1为根节点时 答案就是dp[1]
//接下来就是换根dp的转移了
//具体的推导还是看之前的文章
//这里直接丢了：dp[to]=dp[x]+size[1]-2*size[to];
struct Edge
{
    int from,to;
};
std::vector<Edge> edge[MAXN];;
void dfs1(int x,int fa)
{
    size[x]=1;
    for(auto t:edge[x])
    {
        int to=t.to;
        if(to==fa)  continue;
        depth[to]=depth[x]+1;
        dfs1(to,x);
        size[x]+=size[to];
    }
}
void dfs2(int x,int fa)
{
    for(auto t:edge[x])
    {
        int to=t.to;
        if(to==fa)  continue;
        dp[to]=dp[x]-2*size[to]+size[1];
        dfs2(to,x);
    }
}
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v;    std::cin>>u>>v;
        edge[u].push_back({u,v});
        edge[v].push_back({v,u});
    }
    dfs1(1,-1);
    for(int i=1;i<=n;i++)   dp[1]+=size[i];
    dfs2(1,-1);
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=std::max(ans,dp[i]);
    }
    std::cout<<ans;
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

Tree with Maximum Cost - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=2e5+10;
const int INF=0x3f3f3f3f;
const int mod=19650827;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
ll dp[MAXN];
ll size[MAXN];
ll depth[MAXN];
ll a[MAXN];
struct Edge
{
    int from,to;
};
std::vector<Edge> edge[MAXN];;
void dfs1(int x,int fa)
{
    size[x]=a[x];
    for(auto t:edge[x])
    {
        int to=t.to;
        if(to==fa)  continue;
        depth[to]=depth[x]+1;
        dfs1(to,x);
        size[x]+=size[to];
    }
}
void dfs2(int x,int fa)
{
    for(auto t:edge[x])
    {
        int to=t.to;
        if(to==fa)  continue;
        dp[to]=dp[x]-(2*size[to]-size[1]);
        dfs2(to,x);
    }
}
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<=n;i++)   std::cin>>a[i];
    for(int i=1;i<n;i++)
    {
        int u,v;    std::cin>>u>>v;
        edge[u].push_back({u,v});
        edge[v].push_back({v,u});
    }
    dfs1(1,-1);
    for(int i=1;i<=n;i++)   dp[1]+=depth[i]*a[i];
    dfs2(1,-1);
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=std::max(ans,dp[i]);
    }
    std::cout<<ans;
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

Centroids - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

后续补

P2986 [USACO10MAR] Great Cow Gathering G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=19650827;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
ll dp[MAXN];
ll size[MAXN];
ll depth[MAXN];
ll c[MAXN];
//其实就是加了权值 但是自己还是犯了不少低级错误
//size[x]改为以x为根的子树所拥有的奶牛数目
//depth 表示的是以1为根节点 x到1的深度
//问题如下
//1 dp[to]=dp[x]-(2*size[to]-size[1])*t.val;
//第一个就是把t.val写成了c[to] 其实应该很容易就明白是t.val才对
//因为算的是总距离 自然是数量*距离 结果却变成了数目*数目
//第二个就是 dp[1]+=depth[i]*c[i];
//这里dp的定义改为总距离 所以需要*c[i]
struct Edge
{
    int from,to;
    ll val;
};
std::vector<Edge> edge[MAXN];;
void dfs1(int x,int fa)
{
    size[x]=c[x];
    for(auto t:edge[x])
    {
        int to=t.to;
        if(to==fa)  continue;
        depth[to]=depth[x]+t.val;
        dfs1(to,x);
        size[x]+=size[to];
    }
}
void dfs2(int x,int fa)
{
    for(auto t:edge[x])
    {
        int to=t.to;
        if(to==fa)  continue;
        dp[to]=dp[x]-(2*size[to]-size[1])*t.val;
        dfs2(to,x);
    }
}
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<=n;i++)   std::cin>>c[i];
    for(int i=1;i<n;i++)
    {
        int a,b,l;    std::cin>>a>>b>>l;
        edge[a].push_back({a,b,l});
        edge[b].push_back({b,a,l});
    }
    dfs1(1,-1);
    for(int i=1;i<=n;i++)   dp[1]+=depth[i]*c[i];
    dfs2(1,-1);
    ll ans=1e15;
    for(int i=1;i<=n;i++)
    {
        ans=std::min(ans,dp[i]);
    }
    std::cout<<ans;
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

P3647 [APIO2014] 连珠线 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

后续补

[ABC220F] Distance Sums 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=2e5+10;
const int INF=0x3f3f3f3f;
const int mod=19650827;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
ll dp[MAXN];
ll size[MAXN];
ll depth[MAXN];
ll a[MAXN];
struct Edge
{
    int from,to;
};
std::vector<Edge> edge[MAXN];;
void dfs1(int x,int fa)
{
    size[x]=1;
    for(auto t:edge[x])
    {
        int to=t.to;
        if(to==fa)  continue;
        depth[to]=depth[x]+1;
        dfs1(to,x);
        size[x]+=size[to];
    }
}
void dfs2(int x,int fa)
{
    for(auto t:edge[x])
    {
        int to=t.to;
        if(to==fa)  continue;
        dp[to]=dp[x]-(2*size[to]-size[1]);
        dfs2(to,x);
    }
}
void solve()
{
    int n;  std::cin>>n;
    //for(int i=1;i<=n;i++)   std::cin>>a[i];
    for(int i=1;i<n;i++)
    {
        int u,v;    std::cin>>u>>v;
        edge[u].push_back({u,v});
        edge[v].push_back({v,u});
    }
    dfs1(1,-1);
    for(int i=1;i<=n;i++)   dp[1]+=depth[i];
    dfs2(1,-1);
    for(int i=1;i<=n;i++)
    {
        std::cout<<dp[i]<<"\n";
    }
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

P1395 会议 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=2e5+10;
const int INF=0x3f3f3f3f;
const int mod=19650827;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
ll dp[MAXN];
ll size[MAXN];
ll depth[MAXN];
struct Edge
{
    int from,to;
};
std::vector<Edge> edge[MAXN];;
void dfs1(int x,int fa)
{
    size[x]=1;
    for(auto t:edge[x])
    {
        int to=t.to;
        if(to==fa)  continue;
        depth[to]=depth[x]+1;
        dfs1(to,x);
        size[x]+=size[to];
    }
}
void dfs2(int x,int fa)
{
    for(auto t:edge[x])
    {
        int to=t.to;
        if(to==fa)  continue;
        dp[to]=dp[x]-2*size[to]+size[1];
        dfs2(to,x);
    }
}
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v;    std::cin>>u>>v;
        edge[u].push_back({u,v});
        edge[v].push_back({v,u});
    }
    dfs1(1,-1);
    for(int i=1;i<=n;i++)   dp[1]+=depth[i];
    dfs2(1,-1);
    ll ans=1e9;
    int p=0;
    for(int i=1;i<=n;i++)
    {
        if(ans>dp[i])
        {
            ans=dp[i];
            p=i;
        }
    }
    std::cout<<p<<" "<<ans;
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

P3047 [USACO12FEB] Nearby Cows G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=19650827;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
//一道略有变式的换根dp
//这里需要考虑距离根节点的距离 所以需要添加一个维度k 表示到根节点距离<=k的节点数权值和
//我们还是进行一样的预处理 以1为根
//先预处理出size数组 size[u][i]表示以u为根节点的子树 距离其<=i的节点数
//注意这里是先默认整棵树是以1为根节点的 需要与上面的dp数组区分开来
//size[x][i]+=size[to][i-1] 1<=i<=k 先预处理出size数组 这是dfs1的任务
//接下来考虑dfs2 我们开始进行换根的操作
//dp[to][i]+=dp[x][i-1]-size[to][i-2] 2<=i<=k
//还得考虑dp[to][1]+=size[x][0] 不然会RE并且少算情况
//为什么还要减去size[to][i-2]呢？ 因为dp[x][i-1]一开始是从1为根节点开始的
//所以我们要减去重复的部分 对应的也就是size[to][i-2]（注意这里还是以1为根哦，所以是size数组，而不是dp数组）
//然后我们再dfs2更新即可
//记得dp数组的预处理

//总结
//1 dfs1是以1为根的总树进行预处理 size数组和dp数组本质上是一样的 只不过size数组加了一个以1为根作为总树的前提
//我们可以根据dp数组的设计 来得出size数组的设计（其实一模一样 只不过加了一个限制条件）
//2 在换根的时候需要考虑清楚各种细节 这道题就是算重的情况
ll dp[MAXN][25];
ll size[MAXN][25];
ll c[MAXN];
int n,k;
struct Edge
{
    int from,to;
};
std::vector<Edge> edge[MAXN];
void dfs1(int x,int fa)
{
    for(int i=0;i<=k;i++)   size[x][i]=c[x];
    for(auto t:edge[x])
    {
        int to=t.to;
        if(to==fa)  continue;
        dfs1(to,x);
        for(int i=1;i<=k;i++)
        {
            size[x][i]+=size[to][i-1];
        }
    }
}
void dfs2(int x,int fa)
{
    for(auto t:edge[x])
    {
        int to=t.to;
        if(to==fa)  continue;
        dp[to][1]+=size[x][0];
        for(int i=2;i<=k;i++)
        {
            dp[to][i]+=dp[x][i-1]-size[to][i-2];
        }
        dfs2(to,x);
    }
}
void solve()
{
    std::cin>>n>>k;
    for(int i=1;i<n;i++)
    {
        int u,v;
        std::cin>>u>>v;
        edge[u].push_back({u,v});
        edge[v].push_back({v,u});
    }
    for(int i=1;i<=n;i++)   std::cin>>c[i];
    dfs1(1,-1);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=k;j++)
        {
            dp[i][j]=size[i][j];
        }
    }
    dfs2(1,-1);
    for(int i=1;i<=n;i++)
    {
        std::cout<<dp[i][k]<<"\n";
    }
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

P6419 [COCI2014-2015#1] Kamp - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

后续补

Maximum White Subtree - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=2e5+10;
const int INF=0x3f3f3f3f;
const int mod=19650827;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
ll dp[MAXN];
ll size[MAXN];
ll a[MAXN];
//做了这么多道题目 对换根dp也有了自己的体会
//1 size数组的定义和dp数组定义一样 所以可以根据dp数组的设计来推导出size数组的设计
//size数组多了一个限制条件 就是它是以为1整棵树的根节点的
//2 根据dp数组的定义 我们也可以对size数组进行预处理 不过偏简单暴力
//这里size的定义是最大化cnt1-cnt2 显然的 我们可以贪心
//if(size[to]>0)    size[x]+=size[to];
//这一步是由dfs1完成的 换句话说dfs1是完成以1为根的整棵树的工作
//dfs2就是换根 建议在推导如何换根时 以x作为整棵树的根节点来进行推导 比较好理解
//那么 换根时 不难想到 可能是由x继承过来 也可能是直接继承自己的size
//但是可能 自己的size可能是负值 所以还得再分类讨论
// if(size[to]>0)
//        {
//            //直接继承自己的size或者dp[x]（也就是父亲的dp）
//            //为什么是这样子？因为如果size[to]大于0 那么肯定包括了 
//            dp[to]=std::max(size[to],dp[x]);
//        }
//        else
//        {
//            //如果不大于0 父亲肯定不包括 但是儿子又必须包括 
//            //所以dp[to]就是max(dp[x]+size[to],size[to])
//            //注意size[to]是最优的情况（前提是以1为根）
//            dp[to]=std::max(size[to],dp[x]+size[to]);
//        }
int n;
struct Edge
{
    int from,to;
};
std::vector<Edge> edge[MAXN];
void dfs1(int x,int fa)
{
    size[x]=a[x];
    for(auto t:edge[x])
    {
        int to=t.to;
        if(to==fa)  continue;
        dfs1(to,x);
        if(size[to]>0)
        {
            size[x]+=size[to];
        }
    }
}
void dfs2(int x,int fa)
{
    for(auto t:edge[x])
    {
        int to=t.to;
        if(to==fa)  continue;
        if(size[to]>0)
        {
            dp[to]=std::max(size[to],dp[x]);
        }
        else
        {
            dp[to]=std::max(size[to],dp[x]+size[to]);
        }
        dfs2(to,x);
    }
}
void solve()
{
    std::cin>>n;
    for(int i=1;i<=n;i++)
    {
        std::cin>>a[i];
        if(a[i]==0) a[i]=-1;
    }
    for(int i=1;i<n;i++)
    {
        int u,v;
        std::cin>>u>>v;
        edge[u].push_back({u,v});
        edge[v].push_back({v,u});
    }
    //memset(dp,-0x3f,sizeof(dp));
    dfs1(1,-1);
    dp[1]=size[1];
    dfs2(1,-1);
    for(int i=1;i<=n;i++)
    {
        std::cout<<dp[i]<<" ";
    }
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}