CSP2025 – 树形 DP

6个月前更新

CSP2025 – 树形 DP

T1 「MXOI Round 1」城市

这个 “树上两点距离之和” 很典，让我们想到换根 DP。

首先求出 \(\text{siz}_u\) 和 \(d_u\)，分别表示子树 \(u\) 的大小和子树所有点到 \(u\) 的距离之和。

接下来求出整棵树的所有点到 \(\boldsymbol u\) 的距离之和。考虑用 \(d_u\) 推出 \(d_v\)，我们发现从 \(d_u\) 到 \(d_v\) 少了 \(\text{siz}_v\) 个 \(w(u,v)\) 的贡献，多了 \(n-\text{siz}_v\) 个 \(w(u,v)\) 的贡献，所以第二遍 DFS 的转移方程就是

\[d_v=d_u+(n-2\times\text{siz}_v)\times w(u,v)~. \]

然后考虑第 \(n+1\) 个点加入的情况。对于新建的 \((k,n+1)\) 这条边，会在 \(\sum d_i\) 的基础上多出 \(2\times\big(d_k+n\times w(k,n+1)\big)\) 的贡献（乘 \(2\) 是因为双向边），于是查询就 \(O(1)\) 了。

总体复杂度 \(O(n)\)。

int siz[MAXN],d[MAXN],ans;
void dfs(int u,int fno){
	siz[u]=1;
	for(int i=head[u];i;i=e[i].to){
		if(e[i].v==fno) continue;
		dfs(e[i].v,u);
		siz[u]+=siz[e[i].v];
		add(d[u],(d[e[i].v]+1ll*siz[e[i].v]*e[i].w%MOD)%MOD);
	}
}
void dfs2(int u,int fno){
	for(int i=head[u];i;i=e[i].to)
		if(e[i].v^fno){
			d[e[i].v]=(d[u]+(n-2ll*siz[e[i].v]%MOD+MOD)%MOD*e[i].w%MOD)%MOD;
			dfs2(e[i].v,u);
		}
}

int main(){
	n=read(),q=read();
	for(int i=1,u,v,w;i<n;++i){
		u=read(),v=read(),w=read();
		addedge(u,v,w);
		addedge(v,u,w);
	}
	dfs(1,0);
	dfs2(1,0);
	for(int i=1;i<=n;++i) add(ans,d[i]);
	while(q--){
		int k=read(),w=read();
		write((ans+2ll*d[k]+2ll*n*w)%MOD);
	}
	return fw,0;
}

T2 [CF1285D] Dr. Evil Underscores

其实这题就是个贪心。首先异或 \(\to\) 字典树。把所有数扔到字典树上，然后按二进制位从高到低贪：如果当前节点有两个儿子，取两个儿子的最小值再加上当前位置的贡献；如果有一个儿子，就填成和这个儿子相同的位，不产生贡献。

就没了。

int n,tot=1;
int trie[MAXN][2];
void insert(int x){
	int p=1;
	for(int i=30;~i;--i){
		int c=(x>>i)&1;
		if(!trie[p][c]) trie[p][c]=++tot;
		p=trie[p][c];
	}
}
int ask(int bit,int p){
	if(bit<0) return 0;
	if(trie[p][0]&&trie[p][1]) return min(ask(bit-1,trie[p][0]),ask(bit-1,trie[p][1]))+(1<<bit);
	if(trie[p][0]) return ask(bit-1,trie[p][0]);
	if(trie[p][1]) return ask(bit-1,trie[p][1]);
	return 0;
}

int main(){
	n=read();
	for(int i=1;i<=n;++i) insert(read());
	printf("%d\n",ask(30,1));
	return 0;
}

T3 P1270 “访问”美术馆

感觉这题的读入难度大于 DP 难度

首先建边的时候就把边权建成 \(2\) 倍，这样就计算了往返的时间。然后树上背包，设 \(f_{i,j}\) 表示节点 \(i\) 剩余时间为 \(j\) 的最大答案。则有转移方程

\[f_{u,i}=\max_{v\in\text{son}_u,w(u,v)\le j\le i}\{f_{u,i-j}+f_{v,j-w(u,v)}\}~. \]

在叶子节点时，初始化边界条件 \(f_{u,i}=\min(a_u,f_{u,i-5}+1)\)。

注意如果转移的时候 \(i\) 从 \(n\) 到 \(w\) 枚举复杂度会假，所以我们需要处理 \(\text{siz}_u\) 表示偷完 \(u\) 点所有的东西再回到 \(u\) 点所需要的时间，然后优化转移上界就不会 T 了。\(j\) 也可以优化。

#include<bits/stdc++.h>
using namespace std;

constexpr int MAXN=6005;
int n,tot=2,son[MAXN],siz[MAXN],f[MAXN][MAXN];
vector<pair<int,int>>g[MAXN];
void init(int u,int fno){
	int w,v;
	scanf("%d%d",&w,&v);
	g[fno].emplace_back(u,w<<1);
	if(v) return son[u]=v,void();
	init(++tot,u);
	init(++tot,u);
}
void dfs(int u){
	if(son[u]){
		siz[u]=son[u]*5;
		for(int i=5;i<=n;++i) f[u][i]=min(son[u],f[u][i-5]+1);
		return;
	}
	for(auto vv:g[u]){
		int v=vv.first,w=vv.second;
		dfs(v);
		siz[u]+=siz[v]+w;
		for(int i=min(n,siz[u]);i>=w;--i)
			for(int j=w;j<=min(i,siz[v]+w);++j)
				f[u][i]=max(f[u][i],f[u][i-j]+f[v][j-w]);
	}
}

int main(){
	scanf("%d",&n);
	init(2,1);
	dfs(1);
	printf("%d\n",f[1][n-1]);
	return 0;
}

T4 [HAOI2015] 树上染色

将 “黑点两两距离” 和 “白点两两距离” 转化为针对边计算贡献，也就是对于每一条边所经过的次数，乘上边权再加起来就是总的答案。

而每一条边被经过的次数等于边的两侧同色点的个数的乘积。于是一条边被经过的次数就是：

\[\mathit{tot}=k(m-k)+(\text{siz}_v-k)(n-m-\text{siz}_v+k) \]

其中 \(m\) 是题目要求选的黑点数，\(\text{siz}_v\) 表示 \(v\) 的子树大小，\(k\) 表示当前子树上已选择的黑点数。

DP 方程又是很熟悉的树上背包。设 \(f_{i,j}\) 表示节点 \(i\) 选 \(j\) 个黑点的答案，有

\[f_{u,j}=\max_{v\in\text{son}_u}\{f_{u,j-k}+f_{v,k}+\mathit{tot}\times w(u,v)\} \]

树上背包需要通过 \(\textbf{siz}\) 优化转移边界。把 \(k=0\) 的情况提到循环外面作为边界的预处理。

ll siz[MAXN],f[MAXN][MAXN];
void dfs(int u,int fno){
	siz[u]=1;
	f[u][0]=f[u][1]=0;
	for(int i=head[u],v,w;i;i=e[i].to){
		if((w=e[i].w,v=e[i].v)==fno) continue;
		dfs(v,u);
		siz[u]+=siz[v];
		for(int j=min(1ll*m,siz[u]);~j;--j){
			if(~f[u][j]) f[u][j]+=f[v][0]+siz[v]*(n-m-siz[v])*w;
			for(int k=min(1ll*j,siz[v]);k;--k)
				if(~f[u][j-k]){
					ll tot=1ll*k*(m-k)+(siz[v]-k)*(n-m-siz[v]+k);
					f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]+tot*w);
				}
		}
	}
}

int main(){
	scanf("%d%d",&n,&m);
	if(n-m<m) m=n-m;
	for(int i=1,u,v,w;i<n;++i){
		scanf("%d%d%d",&u,&v,&w);
		addedge(u,v,w),addedge(v,u,w);
	}
	memset(f,-1,sizeof(f));
	dfs(1,0);
	printf("%lld\n",f[1][m]);
	return 0;
}

T9 P5007 DDOSvoid 的疑惑

手画一下发现一定是同父亲的两个子树之间会产生贡献，这个贡献的产生方式为：在这些子树中任选一些，把这些子树的权值加起来就是贡献。

于是，我们需要记录两个值：\(f_u\) 和 \(g_u\)，分别表示节点 \(u\) 的贡献和 “毒瘤集” 的数量。先考虑 \(g_u\) 的转移。把上面所说的 “任选一些” 转化为：每新增一个点 \(v\)，都可以和已有的所有点相匹配，所以有

\[g_u\gets g_u+g_u\times g_v~. \]

然后考虑 \(f_u\) 的转移，依然是每新增一个点都可以和之前的所有点匹配，有

\[f_u\gets f_u+f_u\times g_v+f_v\times g_u+f_v~. \]

至于这里为什么要分别算两遍 \(f_u\times g_v\) 和 \(f_v\times g_u\)，个人认为是因为多个元素构成的集合所产生的贡献也是多个元素的，所以匹配两遍才不会算漏。但为什么不会算重，题解区好像没有合理的解释，只能说 DP 还是太深奥了。

最后还需要给 \(f,g\) 加上当前点的贡献。

ll f[MAXN],g[MAXN];
void dfs(int u,int fno){
	for(int i=head[u],v;i;i=e[i].to){
		if((v=e[i].v)==fno) continue;
		dfs(v,u);
		add(f[u],f[u]*g[v]%MOD+f[v]*g[u]%MOD+f[v]);
		add(g[u],g[u]*g[v]%MOD+g[v]);
	}
	add(f[u],T?u:1);
	++g[u];
}

int main(){
	n=read(),T=read();
	for(int i=1,u,v;i<n;++i){
		u=read(),v=read();
		addedge(u,v),addedge(v,u);
	}
	dfs(1,0);
	printf("%lld\n",f[1]);
	return 0;
}

来源链接：https://www.cnblogs.com/laoshan-plus/p/18593615

评分

欢迎为Ta评分