还在更新ing
前言
此乃小 Oler 的一篇小小算法随笔，从今日后，还会进行详细的修订。
一、简单介绍（change root dp）
如需了解树形dp的，本蒟蒻毛遂自荐，万字大文动态规划【树形dp】Tree DP ~~~详解
换根dp，又叫二次扫描，是树形DP的一种，是一种用来求解树上各点到其他点的距离之和的算法。
其相比于一般的树形DP具有以下特点：
- 以树上的不同点作为根，其解不同。
- 故为求解答案，不能单求某点的信息，需要求解每个节点的信息。
- 故无法通过一次搜索完成答案的求解，因为一次搜索只能得到一个节点的答案。
二、代码实现
引入
T1. 深度最大
描述
给定一个 \(n\) 个点的树，请求出一个结点，使得以这个结点为根时，该树深度最大。深度定义为叶子节点到根的简单路径上边的数量最大值。
输入格式
第一行有一个整数，表示树的结点个数 \(n\) 。
接下来 \((n−1)\) 行，每行两个整数 \(u\) , \(v\) ，表示存在一条连接 \(u\) , \(v\) 的边。
输出格式
输出一行一个整数表示你选择的结点编号。如果有多个结点符合要求，输出节点编号最小值。
输入/输出样例
输入 #1
5
1 2
1 3
2 4
2 5
输出 #1
3
说明/提示
数据规模与约定
对于 \(100\%\) 的数据，保证 \(1≤n≤10^6，1≤u,v≤n\) 。
思路
先简单说说题意，找出对于树上任意节点 \(v_i\) 到所有的叶子节点，使其路径上所经过的节点数量最多的叶子节点，就是 \(\max(maxx|value<v_i,v_j | \in V>)\) ，这里 \(value<v_i,v_j | \in V>\) 指的是当前 \(v_i\) 到所有的叶子节点 \(v_j \in V\) 经过的节点数量。
I.初始化
由于这是一棵无根树，我们假设 \(1\) 为根节点开始进行计算。
①. \(g_{i,0/1}\) 表示以 \(i\) 为根节点的子树的最大深度和次大深度。
②. \(d_i\) 表示以 \(i\) 为根节点的子树的最大深度所经过第一个子节点的编号。
③. \(f_i\) 表示以 \(i\) 为根节点的整棵树的最大深度。
II.First Dfs
这个 dfs 是用于记录以 \(1\) 为根节点的树上，任意节点以自己为根节点的子树的最大和次大深度，父节点的状态由子节点转移过来， \(g_{u,0/1} \gets g_{v,0/1}\) 。
若子节点 \(v\) 的最大深度加上到父节点 \(u\) 的距离，大于节点 \(u\) 以前的最大深度，即 \(g_{u,0}<g_{v,0}+1\) ，则更新 \(g_{u,1}=g_{u,0} ,g_{u,0}=g_{v,0}+1,d_u=v\) 。
否则，就和父节点 \(u\) 以前的次大深度进行比较，\(g_{u,1}=\max(g_{u,1},g_{v,0}+1)\) 。
III.Second Dfs
第二个 dfs 真正意义上体现了“换根”，记录整棵树依次以树上任一节点为根的最大深度，子节点的状态是由父亲转移过来的， \(f_v \gets f_u\) 。
这里第一次 dfs 所记录的 \(g,d\) 就可以排上用场了，由于在上个 dfs 只对当前子树的的叶子节点进行了操作，所以这次固然要对非当前子树的叶子节点遍历。
若父节点 \(u\) 的最大深度经过子节点 \(v\) 即 \(d_u=v\) ，说明这条最大深度的路径上必然包含以 \(v\) 为根的子树，再计算就会重复记录最大深度，这时，我们退而选其次大深度， \(f_v=\max(g_{u,1}+1,f_{v})\) 。
反之，\(d_u \neq v\) 直接取走以节点 \(u\) 为子树的最大深度，即 \(f_v=\max(g_{u,0}+1,f_{v})\) 。
深度最大
最后比较以 \(i\) 为根的子树和整棵树，去其中所有 \(i\) 的最大值。
图例注释：红色箭头表示第一次 dfs 的转态转移，即 \(g\) 数组。
蓝色箭头表示第二次 dfs 的状态转移，即 \(f\) 数组。
Code T1
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,x,y,z;
struct Edge {
int to,nxt,w;
Edge() {
to=nxt=w=0;
}
Edge(int a,int b,int c) {
to=a;
nxt=b;
w=c;
}
}edge[N<<1];
int head[N],idx;
int g[N][2],f[N];
int d[N],ans,p;
void add(int x,int y,int z) { //邻接表存图
edge[++idx]=Edge(y,head[x],z);
head[x]=idx;
}
void dfs_down(int u,int fa) { //求以i为根的子树的最大深度
g[u][0]=g[u][1]=1;
for(int i=head[u];i;i=edge[i].nxt) {
int v=edge[i].to;
int w=edge[i].w;
if(v==fa) continue;
dfs_down(v,u);
if(g[v][0]+w>g[u][0]) {
g[u][1]=g[u][0];
g[u][0]=g[v][0]+w;
d[u]=v;
} else {
if(g[v][0]+w>g[u][1])
g[u][1]=g[v][0]+w;
}
}
return ;
}
void dfs_up(int u,int fa) { //求以i为跟的整棵树的最大深度
for(int i=head[u];i;i=edge[i].nxt) {
int v=edge[i].to;
int w=edge[i].w;
if(v==fa) continue;
f[v]=f[u]+w;
if(d[u]==v)
f[v]=max(g[u][1]+w,f[v]);
else f[v]=max(g[u][0]+w,f[v]);
dfs_up(v,u);
}
}
signed main() {
scanf("%lld",&n);
for(int i=1;i<n;i++) {
scanf("%lld%lld",&x,&y);
add(x,y,1);
add(y,x,1);
}
dfs_down(1,0);
dfs_up(1,0); //遍历整棵树
for(int i=1;i<=n;i++) { //取以i为子树和整棵树中的最大深度
int w=max(g[i][0],f[i]);
if(ans<w) ans=w,p=i; //记录节点编号
}
printf("%lld\n",p);
return 0;
}
T2. [POI2008] STA-Station
题目描述
给定一个 \(n\) 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。
一个结点的深度之定义为该节点到根的简单路径上边的数量。
输入格式
第一行有一个整数，表示树的结点个数 \(n\)。
接下来 \((n - 1)\) 行，每行两个整数 \(u, v\)，表示存在一条连接 \(u, v\) 的边。
输出格式
本题存在 Special Judge。
输出一行一个整数表示你选择的结点编号。如果有多个结点符合要求，输出任意一个即可。
样例 #1
样例输入 #1
8
1 4
5 6
4 5
6 7
6 8
2 4
3 4
样例输出 #1
7
提示
样例 1 解释
输出 \(7\) 和 \(8\) 都是正确答案。
数据规模与约定
对于全部的测试点，保证 \(1 \leq n \leq 10^6\)，\(1 \leq u, v \leq n\)，给出的是一棵树。
实现流程
①. 子树的深度和
先钦定 \(1\) 为整棵树的根，枚举树中以 \(i\) 为根的子树中 \(i\) 到当前子树的各个叶子节点的深度和。
- \(dep_i\) 表示以 \(i\) 为根的子树的深度和。
- \(sz_i\) 表示以 \(i\) 为根的子树中的节点数量；
- \(g_i\) 表示以 \(i\) 为根的子树的中的所有节点到根的距离和。
结合下图，已知 \(g_4\) 和 \(g_5\) 的值，设 \(w_{5 \to 2}\) 为 \(a\)，\(w_{4 \to 2}\) 为 \(b\)。
则易知 \(g_2\) 的深度和肯定由两个子节点的子树的深度和所转移过来；
节点 \(2\) 到节点 \(6\) 的深度为 \(g_4+a \times sz_4\)；同理，节点 \(2\) 到叶子节点 \(7\) 和 \(8\) 的深度为 \(g_5+b \times sz_5\)。
由此可推出转移式：
\(\begin{cases}
g_u=\sum T_u \in g_v +sz_v \times w_{v \to u}\\
sz_u=\sum T_u \in sz_v
\end{cases}\)
②. 整棵树的深度和
遍历树上的所有节点 \(i\)，并求出以该节点作为根节点时的整棵树的深度之和。
- \(f_i\) 表示以 \(i\) 为根的整棵树的深度之和。
预处理：
\(f_1=\textstyle \sum_{i=1}^{n}\)
我们可以通过下图的视角转换中可以发现，在以 \(2\) 为根的整棵树的时候需要求的深度和还需包含节点 \(1\) 为根的子树的深度和，而基于此前的 \(g_2\) 并不可以直接求出此时的深度和。
由于还是从 \(1\) 开始进行遍历，所以我们
再结合下图，可以把以 \(2\) 为根的子树设为 \(A\)，把非此子树的部分设为 \(B\)，\(C\) 表示 \(A\) 与 \(B\) 之间所连接的路径。
易推出方程式是：
\(f_v=A+B+C=g_v+f_u-g_v-sz_v \times w_{v \to u}+(n-sz_v) \times w_{v \to u}\)
化简而得：\(f_v=f_u+(n-2 \times sz_v) \times w_{v \to u}\)
Code T2
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,x,y;
struct Edge {
int to,nxt;
Edge() {
to=nxt=0;
}
Edge(int a,int b) {
to=a;
nxt=b;
}
}edge[N<<1];
int head[N],idx;
int f[N],dep[N];
int res[N],ans,p;
void add(int x,int y) {
edge[++idx]=Edge(y,head[x]);
head[x]=idx;
}
void dfs(int u,int fa) {
res[u]=1;
dep[u]=dep[fa]+1;
for(int i=head[u];i;i=edge[i].nxt) {
int v=edge[i].to;
if(v==fa) continue;
dfs(v,u);
res[u]+=res[v];
}
}
void dfs_(int u,int fa) {
for(int i=head[u];i;i=edge[i].nxt) {
int v=edge[i].to;
if(v==fa) continue;
f[v]=f[u]+n-2*res[v];
dfs_(v,u);
}
}
signed main() {
scanf("%lld",&n);
for(int i=1;i<n;i++) {
scanf("%lld%lld",&x,&y);
add(x,y),add(y,x);
}
dfs(1,0);
for(int i=1;i<=n;i++)
f[1]+=dep[i];
dfs_(1,0);
for(int i=1;i<=n;i++) {
if(ans<f[i]) {
ans=f[i];
p=i;
}
}
printf("%lld\n",p);
return 0;
}