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;
}