换根DP

树形 DP 中的换根 DP 问题又被称为二次扫描，通常不会指定根结点，并且根结点的变化会对一些值，例如子结点深度和、点权和等产生影响。

他相比于相比与一般的树形dp拥有以下特点

  • 以树上不同点作为根，他的解不同
  • 求解答案，不能单求解某点的信息，需要求解每个节点的信息。
  • 无法用一次搜索完成答案求解。

难度不算太高

1.例题引入

P3478 [POI 2008] STA-Station

给定一个 nn 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。

一个结点的深度之定义为该节点到根的简单路径上边的数量。

我们先假设某个节点为根（例如1为根），将无根树转换为有根树，再通过一次DFS搜索出以该节点的深度和，时间复杂度O(n)O(n)

但问题是我们无法确定以该点为根时一定能得到最优解，如果可以的话可以拿样例推推，可以显然发现以任意点为根无法确定是最优解（例如从1开始）

没错这个树长得很奇怪。

我们可以在第二次搜索时完成对答案的统计。

  • 我们假设第一次搜索我们从1号节点出发，通过一次搜索我们就可以获得所有节点子树的大小与节点深度，代码如下：
1
2
3
4
5
6
7
8
9
10
void dfs1(int u,int fa){
    siz[u]=1;
    dep[u]=dep[fa]+1;
    for(auto v:adj[u]){
        if(fa!=v){
            dfs1(v,u);
            siz[u]+=siz[v];
        }
    }
}

  • 第二次搜索依旧从1号节点开始，若1号节点与节点x联通，我们考虑能不能从1号节点的答案推出节点x的答案，如下图

  • 假设这时候我们将根节点换为xx节点，那么该节点子树就会分成两部分。一部分是原来的子树，一部分是1号节点的其他子树

    根从1号节点变为xx节点的时候，我们发现xx原来的子树的深度都降低了1，而11号节点的深度增加1。

递推公式即可得:ans[v]=ans[u]−siz[v]+(siz[1]−siz[v])ans[v]=ans[u]-siz[v]+(siz[1]-siz[v])

不了解？我们一个一个来解释
首先我们要求解的是深度和，我们由uu推的vv的答案，那么我们首先需要以uu作为根节点的答案。

减去siz[v]siz[v]是因为对于vv节点的原子树，我们对其在处理深度时应当全部减1，故减去siz[v]siz[v]（根节点自己也算，他的深度减去就是0）

siz[1]siz[1]表示这个图所有的点数，减去siz[v]siz[v]就是除原子树外与vv节点链接的其他子树，可以相当于上图的橙色链。

化简即得ans[v]=ans[u]+siz[1]−2×siz[v]ans[v]=ans[u]+siz[1]-2\times siz[v]

故代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<vector>
#define ull long long
using namespace std;
const int MN=1e6+15;
vector<int> adj[MN];
ull n,ans[MN],siz[MN],dep[MN];
void dfs1(int u,int fa){
    siz[u]=1;
    dep[u]=dep[fa]+1;
    for(auto v:adj[u]){
        if(fa!=v){
            dfs1(v,u);
            siz[u]+=siz[v];
        }
    }
}
void dfs2(int u,int fa){
    for(auto v:adj[u]){
        if(fa!=v){
            ans[v]=ans[u]+siz[1]-2*siz[v];
            dfs2(v,u);
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs1(1,0);
    for(int i=1;i<=n;i++){
        ans[1]+=dep[i];
    }
    dfs2(1,0);
    ull maxx=-1e13,p;
    for(int i=1;i<=n;i++){
        if(ans[i]>maxx){
            maxx=ans[i];
            p=i;
        }
    }
    cout<<p;
    return 0;
}

2.例题引入的总结

我们看出换根dp的套路

  1. 指定某个节点为根节点
  2. 第一次搜索完成预处理，处理出子树大小等信息，同时得到该节点的解
  3. 第二次搜索进行换根的DP，用已知解的信息推出未知解的答案

3.例题1——P2986 [USACO10MAR] Great Cow Gathering G

每个奶牛居住在NN 个农场中的一个，这些农场由N−1N-1 条道路连接，并且从任意一个农场都能够到达另外一个农场。道路ii 连接农场AiA_i 和BiB_i，长度为LiL_i。集会可以在NN 个农场中的任意一个举行。另外，每个牛棚中居住着CiC_i 只奶牛。

在选择集会的地点的时候，Bessie 希望最大化方便的程度（也就是最小化不方便程度）。比如选择第XX 个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和（比如，农场ii 到达农场XX 的距离是2020，那么总路程就是Ci×20C_i\times 20）。帮助 Bessie 找出最方便的地点来举行大集会。

这个题我们需要维护一个disdis变量表示从其他节点走到当前节点的距离，这个变量我们只需要在第一次搜索时使用即可。这个变量是为了统计出其他子树的奶牛到当前节点的距离。

我们考虑递推公式，我们发现在换根的时候会有相应的边权加减，例如下图

故显然得到递推方程

ans[v]=ans[u]+(1−2×siz[v])∗Edge（u,v）ans[v]=ans[u]+(1-2\times siz[v])*Edge_{（u,v）}
也就是说要乘上边权

故有代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct edge
{
    int v,w;
};

ll n,siz[MN],dis[MN],c[MN],ans[MN],minn=1e16;
vector<edge> adj[MN];

void dfs1(int u,int fa){
    siz[u]=c[u];
    for(auto v:adj[u]){
        if(v.v!=fa){
            dfs1(v.v,u);
            siz[u]+=siz[v.v];
            dis[u]+=dis[v.v]+siz[v.v]*v.w;
        }
    }
}
void dfs2(int u,int fa){
    for(auto v:adj[u]){
        if(v.v!=fa){
            ans[v.v]=ans[u]+(siz[1]-2*siz[v.v])*v.w;
            dfs2(v.v,u);
        }
    }
}

初始化ans[1]=dis[1]ans[1]=dis[1]

4.例题2——CF1324F

给定一棵nn 个节点无根树，每个节点uu 有一个颜色aua_u，若aua_u 为00 则uu 是黑点，若aua_u 为11 则uu 是白点。
对于每个节点uu，选出一个包含uu 的连通子图，设子图中白点个数为cnt1cnt_1，黑点个数为cnt2cnt_2，请最大化cnt1−cnt2cnt_1 - cnt_2。并输出这个值。
1≤n≤2×1051 \leq n \leq 2 \times 10^5，0≤au≤10 \leq a_u \leq 1。

要求最大化cnt1−cnt2cnt_1-cnt_2，不妨设白点带来的权值是+1+1，黑点带来的权值是−1-1。

对于这道题而言，我们任意选取节点作为根，所得到的答案也各不相同。

故设状态f[u]f[u]表示以u为根节点，走uu子树能得到的最大值，故初始值我们就设f[u]=color[u]f[u]=color[u]，color就是上面颜色所带来的权值，这里我们先设根节点为1，故第一次dfs我们能得到f[1]f[1]的答案，但是对于其他节点来时f[v]f[v]并不是以u为根节点，而是只走其子树的答案。不理解看下图：

但是我们维护的是最大值，也就是说我们尽量不加答案为负的子树的答案，也就是我们需要判断以下，看代码。

1
2
3
4
5
6
7
8
void dfs1(int u,int fa){
    f[u]=c[u] ? 1 : -1;
    for(auto v:adj[u]){
        if(fa==v) continue;
        dfs1(v,u);
        f[u]+=max(f[v],0);
    }
}

我们开始考虑转移，我们开始考虑每个子树对于根节点的贡献，我们发现在第一次dfs如果权值为正那么子树答案是必定算上的。故如果当前节点的f[v]f[v]为正的话那么f[u]f[u]应当减去当前节点的贡献。

计算完毕后我们开始考虑以当前点为根，还是和第一次dfs转移一样，尽量不加答案为负子树的答案，这点同样适用于f[v]f[v]从f[u]f[u]转移过来。



故代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dfs2(int u,int fa){
    for(auto v:adj[u]){
        if(fa==v) continue;
        int fu=f[u],fv=f[v];
        if(fv>0){
            fu-=fv;
        }
        if(fu>0){
            fv+=fu;
        }
        f[v]=ans[v]=fv;
        dfs2(v,u);
    }
}

参考：【朝夕的ACM笔记】动态规划-换根DP