树形DP小结

本文用于记录一些做过的树形dp题

一些基础模型

树的最大独立集

设$f[u][1/0]$表示点$u$选/不选，以$u$为根的子树中的最大独立集

f [ u ] [ 0 ] = ∑ m a x { f [ v ] [ 0 ] , f [ v ] [ 1 ] } f[u][0]=\sum max\{f[v][0],f[v][1]\} f[u][0]=∑max{f[v][0],f[v][1]}
$f[u][1]=1+\sum f[v][0]$

树的最小点覆盖集

设$f[u][1/0]$表示点$u$选/不选，以$u$为根的子树中的最小点覆盖集

$f[u][0]=\sum f[v][1]$
f [ u ] [ 1 ] = 1 + ∑ m i n { f [ v ] [ 0 ] , f [ v ] [ 1 ] } f[u][1]=1+\sum min\{f[v][0],f[v][1]\} f[u][1]=1+∑min{f[v][0],f[v][1]}

树的重心

一些做题技巧

1. 对于断边问题，我们有两种处理思路：一种是把边的贡献放在儿子上，令一种是先断掉所有边然后把边的贡献放在父亲上
2. 多叉树转二叉树——左儿子右兄弟表示法

void Pre(int x){//多叉树转二叉树
    vis[x]=true;
    for(int i=1;i<=n;i++)
        if(!vis[i]&&graph[x][i]){
            r[i]=l[x];
            l[x]=i;
            Pre(i);
        }
    return;
}
1
2
3
4
5
6
7
8
9
10

多叉树转二叉树后的最小可能深度

3. 开动态栈记录祖先
   [IOI2005]Riv 河流

树形背包

void dfs(int u,int fa){//树形背包基本模板
	siz[u]=1;
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].v;
		if(v==fa) continue;
		dfs(v,u);
		for(int j=0;j<=min(m,siz[u]);j++){
			for(int k=0;k<=min(m-j,siz[v]);k++){
				//f[u][j+k] <-- w(f[u][j],f[v][k])
			}
		}
		siz[u]+=siz[v];
	} 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度
$={\sum }_i{\sum }_{j,k\in so{n}_i}si{z}_j\times si{z}_k$
$={\sum }_i{\sum }_{j,k\in so{n}_i}({\sum }_x[x\in subtre{e}_j])\times ({\sum }_y[y\in subtre{e}_j])$
因为$LCA(x,y)=i$，即任何两点只在$lca$处有贡献
所以时间复杂度是$O(n^2)$的

[CTSC1997]选课

LuoguP1273 有线电视网

[JSOI2008]魔兽地图

换根dp

经典例题：给定一棵树，对于每个点，求该点到与它距离最远的点的距离。
用$f[x][0]$表示 $x$的子树中 的点到$x$的最远距离，用$f[x][1]$表示 $x$的子树中 的点到$x$的次远距离，用$f[x][2]$表示 不在$x$的子树中 的点到$x$的最远距离。
第一次dp求出$f[x][0],f[x][1]$，第二次dp用父亲的$f[fa][0],f[fa][1]$求出儿子的$f[x][2]$。
最后答案即为 $max(f[x][0],f[x][2])$

基环树

虚树

//虚树板子
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=1e6+10;
const ll inf=1e14;
int n,q,k,p[N];
int to[N<<1],nxt[N<<1],head[N],cnt=0;
int fa[N][25],dep[N],dfn[N],ind=0;
int st[N],top=0;
bool key[N];
ll d[N],f[N],g[N],siz[N];
ll ans1,ans2,ans3;
struct edge{int v,len;};
vector<edge> ge[N];
int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
void add(int u,int v){
    to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
void dfs1(int u,int f){
    dfn[u]=++ind;
    for(int i=1;i<=22;i++){
        if(dep[u]<(1<<i)) break;
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(v==f) continue;
        fa[v][0]=u;
        dep[v]=dep[u]+1;
        dfs1(v,u);
    }
}
int LCA(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    int diff=dep[u]-dep[v];
    for(int i=22;i>=0;i--){
        if(diff&(1<<i)) 
            u=fa[u][i];
    }
    if(u==v) return u;
    for(int i=22;i>=0;i--){
        if(fa[u][i]!=fa[v][i]) {
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return fa[u][0];
}
bool cmp(int a,int b){
    return dfn[a]<dfn[b];
}
int dist(int u,int v){
    if(dep[u]>dep[v]) swap(u,v);
    return dep[v]-dep[u];
}
void add2(int u,int v,int l){
    if(dep[u]>dep[v]) swap(u,v);
    ge[u].push_back((edge){v,l}); 
}
inline void insert(int x){
	if(!top){st[++top]=x;return;}
	int lca=LCA(st[top],x);
	while(top>1&&dep[st[top-1]]>dep[lca]){
		add2(st[top-1],st[top],dist(st[top-1],st[top]));
		top--;
	}
	if(dep[lca]<dep[st[top]]){
		add2(lca,st[top],dist(lca,st[top]));
		top--;
	}
	if(!top||dep[st[top]]<dep[lca]) st[++top]=lca;
	st[++top]=x;
}
void dfs2(int u){
    siz[u]=key[u];
    d[u]=g[u]=0; 
    f[u]=key[u]?0:inf;
    for(int i=0;i<ge[u].size();i++){
        int v=ge[u][i].v;
        int w=ge[u][i].len;
        dfs2(v);
        if(siz[u]>0){
            ans1+=siz[u]*siz[v]*w+siz[v]*d[u]+siz[u]*d[v];
            ans2=min(ans2,f[u]+w+f[v]);
            ans3=max(ans3,g[u]+w+g[v]);
        }
        d[u]+=d[v]+siz[v]*w;
        f[u]=min(f[u],w+f[v]);
        g[u]=max(g[u],w+g[v]);
        siz[u]+=siz[v];
    }
    ge[u].clear();key[u]=0;
}
int main(){
    n=read();
    int a,b;
    for(int i=1;i<n;i++){
        a=read();b=read();
        add(a,b);add(b,a);
    }
    dfs1(1,0);
    q=read();
    while(q--){
        k=read();
        for(int i=1;i<=k;i++) p[i]=read();
        sort(p+1,p+k+1,cmp);
        if(p[1]!=1) st[top=1]=1;
        else st[top=0]=0;
        for(int i=1;i<=k;i++) insert(p[i]),key[p[i]]=1;
        while(top>1) add2(st[top-1],st[top],dist(st[top-1],st[top])),--top;
        ans1=0;ans2=inf;ans3=0;
        dfs2(1);
        printf("%lld %lld %lld\n",ans1,ans2,ans3);
    }
    return 0;
}
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

树上动态dp

树上最优选点/选边问题

[POI2011] DYN-Dynamite
CF671D 【Roads in Yusland】

• 树上选不相交链问题
  该问题满足最优子结构，即如果要在$u$的子树里面选链，我们可以先对$u$的每一个儿子$v$的子树求出最优解，再在$u$子树的剩余未选择部分里面选链。
  P5021 [NOIP2018 提高组] 赛道修建
  XSY4197 Snow

与树有关的区间dp

$f[i][j]$表示节点i到节点j构成树的贡献，按照区间长度从小到大的顺序进行区间dp。
[NOIP2003 提高组] 加分二叉树
$f[i][j]$表示节点i到节点j构成树的最大加分。
二叉树的加分取决于谁是根，于是我们在区间内枚举根$k$来转移：
$f[i][i]=a[i]$
f [ i ] [ j ] = m a x { f [ i ] [ k − 1 ] × f [ k + 1 ] [ j ] + f [ k ] [ k ] } ( i ≠ j ) f[i][j]=max\{f[i][k-1]\times f[k+1][j]+f[k][k]\}(i\not=j) f[i][j]=max{f[i][k−1]×f[k+1][j]+f[k][k]}(i​=j)