换根dp

-1 前言

迅速糊出来的一篇东西。

算得上是朝花夕拾了。

0 前置知识

• 树形DP

1 什么是换根DP

一般来讲,树形DP都是记录一个点的状态,然后在遍历这棵树的过程中转移到相邻的点.

通常,大部分的树形DP题目都会指定或者有一个固定的根.但还有一部分题目,通常不会指定根节点,或者说根节点不是固定的,并且根节点的变化会对树上的一些信息产生影响(比如节点深度).这种题目需要记录根节点的状态,通过转移根节点来的出答案.这种方法称为换根DP.

换根DP,顾名思义,就是需要通过不断的"换根",即转移根节点,来得出答案.

2 换根DP的实现

处理换根DP的问题时,我们通常进行两次DFS.第一次DFS处理出转移所需的信息,比如每个节点的深度,子树大小等信息.第二次DFS开始进行DP,分别考虑以每个点为根时的答案,然后将当前点为根的状态转移到相邻的点上.这种做法称为二次扫描.

来看一道换根DP的板子题------STA-Station

看到这道题,我们首先来想状态和边界.

状态很好设计,$f_i$ 表示以 $i$ 为根时整颗树的深度和.假如我们一开始钦定1为最初的根节点,那么边界条件就是 $f_1=\sum dep_i$.

然后我们来考虑如何转移.

如图,假如我们原本的根是 $i$,现在要转移到 $j$,那么显然的, $j$及其子树(即绿圈部分)的深度就会减去1,而除了这一部分的其他部分(即红圈部分)深度就会加上1.

我们用 $siz_i$ 表示 $i$ 的子树大小.那么显然的,由于 $j$ 及其子树共有 $siz_j$ 个节点,那么这一部分会给 $f_j$ 造成 $-siz_j$ 的贡献.同样的,除此之外的其他部分也会给 $f_j$ 造成 $(n-siz_j)$ 的贡献.

所以,我们可以列出状态转移方程:

$$f_j=f_i-siz_j+(n-siz_j)$$

化简得:

$$f_j=f_i+n-siz_j\cdot2$$

然后我们就可以对此进行转移.

于是,我们需要在第一遍DFS中预处理出两个信息:

• $dep_i$ :第 $i$ 个节点的深度

• $siz_i$ :第 $i$ 个节点的子树大小

直接处理即可,代码如下:

void dfs0(int now,int fa){
    siz[now]=1,dep[now]=dep[fa]+1;
    for(auto &i:g[now]){
        if(i==fa)continue;
        dfs0(i,now);
        siz[now]+=siz[i];
    }
}

然后我们处理出边界条件 $f_1=\sum dep_i$,接着进行第二遍DFS.

假设现在我们遍历到点 $now$,这个节点目前遍历到的的儿子是 $i$,那么我们就来计算:

$$f_i=f_{now}+n-f_i\cdot 2$$

然后再遍历计算点 $i$ 及其儿子.如此循环往复,代码如下:

void dfs1(int now,int fa){
    for(auto &i:g[now]){
        if(i==fa)continue;
        f[i]=f[now]-siz[i]+n-siz[i];
        dfs1(i,now);
    }
}

然后主函数计算 $max\{f_i\}$ 然后输出答案.最终代码如下:

#include <bits/stdc++.h>
using namespace std;
#define int long long
int read(){
    int f=1,s=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){s=(s<<1)+(s<<3)+(c-'0');c=getchar();}
    return f*s;
}
vector<int> g[1919810];
int n,f[1919810],ans,maxx=-0x3f3f3f3f,dep[1919810],siz[1919810];
void dfs0(int now,int fa){
    siz[now]=1,dep[now]=dep[fa]+1;
    for(auto &i:g[now]){
        if(i==fa)continue;
        dfs0(i,now);
        siz[now]+=siz[i];
    }
}

void dfs1(int now,int fa){
    for(auto &i:g[now]){
        if(i==fa)continue;
        f[i]=f[now]+n-siz[i]*2;
        dfs1(i,now);
    }
}
signed main(){
    n=read();
    for(int i=1;i<n;++i){
        int u=read(),v=read();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs0(1,0);
    for(int i=1;i<=n;++i){
        f[1]+=dep[i];
    }
    dfs1(1,0);
    for(int i=1;i<=n;++i){
        if(f[i]>maxx)maxx=f[i],ans=i;
    }
    cout<<ans;
}  

于是本题结束.

本题之所以可以算做换根DP板子题是因为足够简单十分经典,基本包含了换根DP的所有基本步骤.

3 应用

实际上,上面那道题就是求树的重心.

这也引申出了换根DP一个比较常见的应用:求树的重心.

上面的例题是不带边权和点权的求树重心.带边权和点权的话只需进行简单处理即可.

4 例题

带点权的求树重心: P1364,T371047

带边权和点权的求树重心: P2986

其他: CF1822F

5 后记

糊出来的东西好像还行。