#创作计划# 换根论
2025-10-24 21:39:26
发布于：浙江
咕咕咕
前言
此部分并不会影响您的阅读，可以跳过
本文默认读者已具备独立写出初阶 DP 的能力
关于创作原因
1.听说 CSP 前发学术内容可以 RP++。
2.@Lyzc0dr
这位的言论让我很红温。
为什么讲换根
因为我们老师最近刚讲换根 DP，打算写一篇来巩固记忆。
正文
1.概念
我们知道 DP 实际上就是对于一个问题的一种动态决策，而换根 DP 顾名思义，就是在树上进行的 DP，而且不会指定某一处作为根，并且根结点的变化会对一些值，例如子结点深度和、点权和等产生影响。
这种 DP 一般会通过 2 次 DFS 来实现，一次初始化，一次进行状态转移。
让我们用一道例题来引入。
2.用法
形式化翻译：
给定一颗 节点的树 ，定义 为从节点 到 的简单路径长度（包括 ），求出：
解法：
显然，根据形式化翻译，我们对于每一个根节点都做一次 DFS 显然是不行的。
那么，根据 DP 的定义，我们可不可以从一个点的最优结果推出另一个点的最优结果呢？
答案是可以的。
如图为样例所代表的树（作者电脑画图技术一坨，所以用手画，望见谅）：
如图，我们显然可以发现若我们从节点 到节点 ，对于 来说，其对答案的贡献就会同时加上 这一段的长度 ；同理，对于 来说，其对答案的贡献就会同时减少 这一段的长度 ，总共的以 为根节点对答案的贡献相对以 为根节点增加
因此，我们就可以用 表示以 ，即以 为根节点的答案。
结合上文对从节点 到节点 的分析，可以引申到如果从 （其中 为 的父亲）去更新 的话，那么相对 来说， 所有以 为根的子树中的节点对答案的贡献都会相对 减少 这一段的长度 。同时，所有不是以 为根的子树中的节点对答案的贡献都会相对 增加 这一段的长度 。
因此，令 为 的子树大小（包括 ）， 为节点 的父亲，那么就有：
其中 可以通过一次 DFS 预处理出来，然后就可以用 DFS 自上而下求出 ，最后的答案就是：
如果不懂的话可以自行画图分析。
知道了思路，你应该就可以自行写代码了吧：）
以防你不会，给出代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,dp[1000010],sz[1000010];
vector<int> tr[1000010];
void dfs1(int u,int fa){
sz[u]=1;
for (int i=0;i<tr[u].size();++i){
int v=tr[u][i];
if (v==fa)continue;
dfs1(v,u);
sz[u]+=sz[v];
dp[u]+=dp[v]+sz[v];
}
}
void dfs2(int u,int fa){
for (int i=0;i<tr[u].size();++i){
int v=tr[u][i];
if (v==fa)continue;
dp[v]=dp[u]-2*sz[v]+n;
dfs2(v,u);
}
}
signed main()
{
cin>>n;
for (int i=1;i<n;++i){
int u,v;
cin>>u>>v;
tr[u].push_back(v);
tr[v].push_back(u);
}
dfs1(1,0);
dfs2(1,0);
int ans=0,idx=0;
for (int i=1;i<=n;++i){
if (ans<dp[i]){
ans=dp[i];
idx=i;
}
}
cout<<idx<<endl;
return 0;
}
为什么不能自底向上搜索
显然，这样的话对于 来说， 在转移过程中的 中又包含其他的 ，具有后效性，不满足 DP 性质。
现在，让我们做一些例题吧.
3.例题
[USACO10MAR] Great Cow Gathering G
和上一题是基本一样的，只不过有了点权，只需要在初始化时令 就可以了，代码基本一样.
有帮助，赞一个