YBTOJ 树形dp合集

qwq

树上求和

设 $f[x][0]$ 为不选 $x$ 时 $x$ 及其子树所能得到的最大权值，$f[x][1]$ 为选 $x$ 是 $x$ 及子树所能得到的最大权值，根据选了儿子就不能选父亲的规则转移一下即可。

结点覆盖

设 $f[x][0]$、$f[x][1]$、$f[x][2]$ 分别表示在 $x$ 及其子树内，使结点 $x$ 被父亲、自己、儿子覆盖所需的最小花费，则有：

• $x$ 被父亲覆盖，儿子要么被自己覆盖要么被儿子的儿子覆盖，即 $f[x][0]+=\min (f[v][1],f[v][2])$；
• $x$ 被自己覆盖，儿子三种情况均可，即 $f[x][1]+=\min (f[v][0],min(f[v][1],f[v][2]))$；
• $x$ 被儿子覆盖，至少有一个儿子要被自己覆盖，其余儿子要么被自己覆盖要么被儿子的儿子覆盖，即 $f[x][2]+=\min (f[v][1],f[v][2])$，当对于每个 $v$ 都取 $f[v][2]$ 的时候是不合法的，所以要额外记录一个值 m i n n = min ⁡ { f [ v ] [ 1 ] − f [ v ] [ 2 ] } minn=\min\{f[v][1]-f[v][2]\} minn=min{f[v][1]−f[v][2]}。

inline void dfs(int x){
	f[x][1]=a[x];
	int flag=0,minn=1e9;
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].v;
		dfs(v);
		f[x][0]+=min(f[v][1],f[v][2]);
		f[x][1]+=min(f[v][0],min(f[v][1],f[v][2]));
		if(f[v][1]<=f[v][2]) flag=1,f[x][2]+=f[v][1];
		else f[x][2]+=f[v][2],minn=min(minn,f[v][1]-f[v][2]);
	}
	if(!flag) f[x][2]+=minn;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

最长距离

到每个结点距离最远的点，要么在它的子树内，要么在它的子树外。

根据这个性质，设 $f[x][0]$、$f[x][2]$ 分别为 $x$ 的子树内和 $x$ 的子树外的点到 $x$ 的最远距离，那么一遍dfs可以很容易求出 $f[x][0]$，求 $f[x][2]$ 也无非两种情况：最远点不在 $x$ 的父亲的子树内，或最远点在 $x$ 的父亲的子树内。设 $x$ 到父亲的距离为 $w$，第一种情况的答案就是 $w+f[fa][2]$，第二种情况的答案就是 $w+$不在 $x$ 的子树内的点到 $fa$ 的距离最大值，有了不在同一子树的限制，就需要在第一次dfs时维护 $f[x][1]$ 作为 $x$ 的子树内的点到 $x$ 的次远距离。

inline void dfs(int x){
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].v,w=e[i].w;
		dfs(v);
		if(f[v][0]+w>=f[x][0]) f[x][1]=f[x][0],f[x][0]=f[v][0]+w;
		else if(f[v][0]+w>f[x][1]) f[x][1]=f[v][0]+w;
	}
}
inline void dfs2(int x,int fa,int w){
	if(f[x][0]+w==f[fa][0]){
		f[x][2]=max(f[fa][2],f[fa][1])+w;
	}
	else f[x][2]=max(f[fa][2],f[fa][0])+w;
	for(int i=head[x];i;i=e[i].nxt) dfs2(e[i].v,x,e[i].w);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

选课方案

树形dp经典问题但是我给忘了

但是可以现场胡：选课之间的依赖关系可以构成森林，建立一个虚拟结点 $0$ 就可以把森林变成一棵以 $0$ 为根的树，问题就变为在这棵树上选 $m+1$ 个点，选了父节点才能选子节点，问怎么选权值和最大。

设 $f[i][j]$ 为在以 $i$ 为根的子树中选 $j$ 个结点能选出的最大值，那么只需要dfs的时候枚举 $j$，再枚举每一个子节点 $v$ 里选的点数 $k$ 进行dp转移即可。时间复杂度 $O(n^3)$。

inline void dfs(int x){
	f[x][1]=a[x];
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].v;
		dfs(v);
		for(int j=m+1;j>=2;--j) ff(k,1,j-1) f[x][j]=max(f[x][j],f[v][k]+f[x][j-k]);
		//因为期望用到的f[x][j-k]都是在不算当前节点v的情况下所获得的最大值，所以要倒着枚举j，保证f[x][j-k]还没被更新
	}
}
1
2
3
4
5
6
7
8
9

路径求和

正解是记录每条边会被计入答案多少次，好巧妙qwq

我的做法：对于每个点分别计算在以它为根的子树内和它的子树外的叶子结点到它的距离和，分别记为 $f[x]$ 和 $g[x]$。

先求解 $f[x]$，可以得到转移式$f[x]={\sum }_{v\in so{n}_x}(f[v]+num[v]\times w)$，其中 $num[i]$ 表示 $i$ 的子树里的叶子结点数，可以事先递归预处理。

再求解 $g[x]$，设 $x$ 的父节点为 $fa$，那么 $x$ 的子树外的叶子结点也有两种情况：在 $fa$ 的子树外和在 $fa$ 的子树内。设总叶子结点数为 $tot$，$x$ 到 $fa$ 距离为 $w$，则这些叶子结点一共有 $tot-num[x]$ 个，所以答案可以初始化为 $w\times (tot-num[x])$。在 $fa$ 的子树外的点的答案即为 $g[fa]$，在 $fa$ 的子树内而不在 $x$ 的子树内的答案即为 ${\sum }_{v\in so{n}_{fa},v\ne x}(f[v]+num[v]\times w)$，然后这道题就解决了（可能算的有点麻烦但是非常好想qwq

树上移动

一个人走，每条路径必须走两次，最后选一条路只走一次，那么必然是从 $s$ 出发的最长路只走一次最优。

两个人走，也是先每条路走两次，然后每个机器人选一条路径走到底，那么必然这两条走到底的路合起来构成树的直径时最优。

所以dfs求最长路和次长路即可。

块的计数

当有多个最大值的时候，重复的贡献不好消去，所以考虑算出一共可以构成的连通块数和不包含最大值的连通块数，相减即为答案。

奇怪的错误出现了：维护两个值，分开写两个dfs就30分，合并成一个dfs就AC？我不李姐。

#include
#define ll long long
#define ff(i,s,e) for(int i=s;i<=(e);++i)
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=1e5+5,mod=998244353;
int n,a[N],maxx=-2147483647;
int head[N],cnt;
struct qwq{
	int v,nxt;
}e[N<<1];
inline void add(int u,int v){
	e[++cnt]=qwq{v,head[u]};
	head[u]=cnt;
}
int sum[N],f[N];
inline void dfs(int x,int fa){
	if(a[x]!=maxx) f[x]=1;
	sum[x]=1;
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fa) continue;
		dfs(v,x);
		f[x]=1ll*(f[v]+1)*f[x]%mod;
		sum[x]=1ll*(sum[v]+1)*sum[x]%mod;
	}
}
signed main(){
	n=read();
	ff(i,1,n) a[i]=read(),maxx=max(maxx,a[i]);
	ff(i,2,n){
		int u=read(),v=read();
		add(u,v),add(v,u);
	}
	dfs(1,0);
	int ans=0;
	ff(i,1,n) ans=(ans+sum[i]-f[i])%mod;
	printf("%d",(ans+mod)%mod);
	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

树的合并

古早题戳这里

权值统计

对于每个点x，统计经过x且路径上x的深度最浅的答案。x深度最浅有两组情况：x是端点或x不是端点。设f[x]为x是端点的情况的答案，则有 $f[x]=({\sum }_{v\in so{n}_x}f[v]+1)\times a[x]$，其中加一是因为要算上只有x自己这种情况。

考虑x不是端点的情况，则路径长这样：/\，权值为左边权值 $\times$ 右边权值 $\times a[i]$，可以表示为 $(({\sum }_{v\in so{n}_x}f[v]{)}^2-$ ${\sum }_{v\in so{n}_x}(f[v]{)}^2)÷2$。

#include
#define ll long long
#define int long long
#define ff(i,s,e) for(int i=s;i<=(e);++i)
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=1e5+5,mod=10086;
int n,a[N];
int head[N],cnt;
struct qwq{
	int v,nxt;
}e[N<<1];
inline void add(int u,int v){
	e[++cnt]=qwq{v,head[u]},head[u]=cnt;
}
int f[N];
ll ans;
inline void dfs(int x,int fa){
	int tot=0,sum=0;
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fa) continue;
		dfs(v,x);
		sum+=f[v],tot+=f[v]*f[v];
	}
	f[x]=(sum+1)*a[x]%mod;
	ans=(ans+((sum*sum-tot)>>1)*a[x]+f[x])%mod;
}
signed main(){
	n=read();
	ff(i,1,n) a[i]=read();
	ff(i,2,n){
		int u=read(),v=read();
		add(u,v),add(v,u);
	}
	dfs(1,0);
	printf("%lld",ans);
	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