【做題記錄】csp2025-樹形dp
A. 「MXOI Round 1」城市
首先推個小式子，把讓求的答案中和 \(n+1\) 有關的分出來：
\[\begin{align*}
&\sum_{i=1}^{n+1}\sum_{j=1}^{n+1}cost(i,j)\\
=&\sum_{i=1}^{n+1}\sum_{j=1}^{n}cost(i,j)+\sum_{i=1}^{n+1}cost(i,n+1)\\
=&\sum_{i=1}^{n}\sum_{j=1}^{n}cost(i,j)+\sum_{i=1}^{n}cost(i,n+1)+\sum_{i=1}^{n+1}cost(i,n+1)\\
=&\sum_{i=1}^{n}\sum_{j=1}^{n}cost(i,j)+2\sum_{i=1}^{n}cost(i,n+1)
\end{align*}
\]
發現前面一部分是可以預先算出來的，考慮后一部分。
發現這一部分相當于是所有點到 \(k\) 的距離，再加上 \(n\times w\)。
于是考慮換根DP，首先計算每個點的子樹的答案，即
\[f[u]=\sum f[v]+sz[v]\times w
\]
然后用父親更新兒子為根時的答案：
\[\begin{align*}
g[v]&=f[v]+(g[u]-f[v]-sz[v]\times w+(n-sz[v])\times w)\\
&=g[u]+(n-2sz[v])\times w
\end{align*}
\]
答案即為
\[\sum_{i=1}^ng[i]+2(g[k]+n\times w)
\]
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e5+5,mod=998244353;
int n,m,sz[maxn],f[maxn];
vector<pii> e[maxn];
il void dfs1(int u,int fa){
sz[u]=1;
for(pii i:e[u]){
int v=i.fir,w=i.sec;
if(v==fa){
continue;
}
dfs1(v,u);
sz[u]+=sz[v];
(f[u]+=f[v])%=mod;
(f[u]+=sz[v]*1ll*w%mod)%=mod;
}
}
il void dfs2(int u,int fa){
for(pii i:e[u]){
int v=i.fir,w=i.sec;
if(v==fa){
continue;
}
f[v]=(f[u]+(n-sz[v]*2+mod)*1ll*w%mod)%mod;
dfs2(v,u);
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n)read(m);
for(int i=1,u,v,w;i<n;i++){
read(u)read(v)read(w);
e[u].pb(mp(v,w));
e[v].pb(mp(u,w));
}
dfs1(1,0),dfs2(1,0);
// for(int i=1;i<=n;i++){
// cout<<f[i]<<" ";
// }
// puts("");
int sum=0;
for(int i=1;i<=n;i++){
(sum+=f[i])%=mod;
}
while(m--){
int u,w;
read(u)read(w);
printf("%d\n",(sum+((f[u]+n*1ll*w%mod)%mod<<1)%mod)%mod);
}
return 0;
}
}
int main(){return asbt::main();}
B. Dr
看到異或首先建trie樹，然后考慮trie樹上從0，1兒子向父親的轉移。
首先如果沒有其中一個，那么直接讓這一位等于有的那一個，即沒有任何多余的貢獻。
否則，要選一個加上2的若干次方，然后取最小值。這一部分的轉移：
\[dp[u]=\min(dp[tr[u][0]],dp[tr[u][1]])+2^{dep}
\]
其中 \(dep\) 是當前的二進制位。不用dfs，倒序遍歷即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5;
int n,a[maxn],tot,tr[maxn<<5][2];
int dp[maxn<<5],dep[maxn<<5];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
int p=0;
for(int j=30;~j;j--){
int d=a[i]>>j&1;
if(!tr[p][d]){
tr[p][d]=++tot;
dep[tot]=j;
}
p=tr[p][d];
}
}
for(int u=tot;u;u--){
if(!tr[u][0]&&!tr[u][1]){
continue;
}
if(!tr[u][0]){
dp[u]=dp[tr[u][1]];
}
else if(!tr[u][1]){
dp[u]=dp[tr[u][0]];
}
else{
dp[u]=min(dp[tr[u][0]],dp[tr[u][1]])+(1<<(dep[u]-1));
}
}
printf("%d",min(tr[0][0]?dp[tr[0][0]]:INT_MAX,tr[0][1]?dp[tr[0][1]]:INT_MAX));
return 0;
}
}
int main(){return asbt::main();}
C. “訪問”美術館
樹上背包。考慮 \(f[u][i]\) 表示在 \(u\) 的子樹中，拿了 \(i\) 幅畫所需的最少時間。答案是好統計的。
則有：
\[f[u][i+j]=f[l][i]+f[r][j]+2(a[l]+a[r])
\]
但是這個時候我們發現一個問題，如果在這個子樹中不拿畫的話，根本就不用進入這個子樹，也就是轉移式中的 \(2a\) 是不用加上的。解決方法是令 \(f[u][0]=-2a[u]\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2005;
int n,tot,f[maxn][maxn];
int a[maxn],b[maxn];
il int dfs(){
int u=++tot;
read(a[u])read(b[u]);
if(b[u]){
for(int i=0;i<=b[u];i++){
f[u][i]=i*5;
}
}
else{
int l=dfs();
int r=dfs();
b[u]=b[l]+b[r];
for(int i=0;i<=b[l];i++){
for(int j=0;j<=b[r];j++){
f[u][i+j]=min(f[u][i+j],f[l][i]+f[r][j]+((a[l]+a[r])<<1));
}
}
}
f[u][0]=-a[u]<<1;
return u;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
// freopen("P1270_5.in","r",stdin);
read(n);
memset(f,0x3f,sizeof f);
int rt=dfs();
for(int i=b[rt];~i;i--){
if(f[rt][i]+(a[rt]<<1)<n){
printf("%d",i);
return 0;
}
}
}
}
int main(){return asbt::main();}
D. 「HAOI2015」樹上染色
考慮一條邊被經過的次數，等于邊兩邊黑點個數之積加上白點個數之積。于是設 \(f[u][i]\) 表示在 \(u\) 的子樹中選了 \(i\) 個點，并且考慮了 \(u\) 的子樹中的邊的答案。這是一個經典的樹上背包。于是有
\(
f[u][j+k]=\max(f[u][j]+f[v][k]+w\times (k\times (m-k)+(sz[v]-k)\times (n-sz[v]-m+k)))
\)
答案即為 \(f[1][m]\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define int ll
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e3+5;
int n,m,f[maxn][maxn],sz[maxn],nf[maxn];
vector<pii> e[maxn];
il void dfs(int u,int fa){
sz[u]=1;
for(pii i:e[u]){
int v=i.fir,w=i.sec;
if(v==fa){
continue;
}
dfs(v,u);
for(int j=0;j<=sz[u]+sz[v];j++){
nf[j]=0;
}
for(int j=0;j<=sz[u];j++){
for(int k=0;k<=sz[v];k++){
nf[j+k]=max(nf[j+k],f[u][j]+f[v][k]+w*(k*(m-k)+(sz[v]-k)*(n-sz[v]-m+k)));
}
}
sz[u]+=sz[v];
for(int j=0;j<=sz[u];j++){
f[u][j]=nf[j];
}
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
read(n)read(m);
for(int i=1,u,v,w;i<n;i++){
read(u)read(v)read(w);
e[u].pb(mp(v,w));
e[v].pb(mp(u,w));
}
dfs(1,0);
printf("%lld",f[1][m]);
return 0;
}
}
signed main(){return asbt::main();}
E. Tree Array
考慮首先枚舉根，然后計算每個逆序對的貢獻。
發現對于一對點 \(u,v\)，從根到 \(lca(u,v)\) 的過程是相同的，因此只需要計算 \(lca(u,v)\to u\)，\(lca(u,v)\to v\) 的過程，最終使得先到達編號較大的就行了。
發現只用考慮對答案有用的部分，其他地方不用關心。然后對于每一步，向 \(u\) 走一步和向 \(v\) 走一步的概率是相同的。因此只用考慮這兩條路徑的長度。設 \(f[i][j]\) 表示 \(u\) 路徑長為 \(i\)，\(v\) 路徑長為 \(j\)，先走到 \(u\) 的概率。有方程：
\[f[i][j]=\frac{f[i-1][j]+f[i][j-1]}2
\]
對于每對點 \(u,v\) 且 \(u>v\)，貢獻即為 \(f[dep[u]-dep[lca(u,v)]][dep[v]-dep[lca(u,v)]]\)。
因為是枚舉根，所以最后要除以 \(n\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=205,mod=1e9+7;
int n,dep[maxn],top[maxn],hes[maxn];
int sz[maxn],fa[maxn],f[maxn][maxn];
vector<int> e[maxn];
il void dfs1(int u){
dep[u]=dep[fa[u]]+1;
sz[u]=1;
int mxs=0;
for(int v:e[u]){
if(v==fa[u]){
continue;
}
fa[v]=u;
dfs1(v);
sz[u]+=sz[v];
if(mxs<sz[v]){
mxs=sz[v],hes[u]=v;
}
}
}
il void dfs2(int u){
if(!top[u]){
top[u]=u;
}
if(hes[u]){
top[hes[u]]=top[u];
dfs2(hes[u]);
}
for(int v:e[u]){
if(v==fa[u]||v==hes[u]){
continue;
}
dfs2(v);
}
}
il int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]){
swap(u,v);
}
u=fa[top[u]];
}
return dep[u]>dep[v]?v:u;
}
il int qpow(int x,int y){
int res=1;
while(y){
if(y&1){
res=res*1ll*x%mod;
}
y>>=1,x=x*1ll*x%mod;
}
return res;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n);
for(int i=1,u,v;i<n;i++){
read(u)read(v);
e[u].pb(v),e[v].pb(u);
}
int inv2=qpow(2,mod-2);
for(int i=0;i<=n;i++){
f[0][i]=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f[i][j]=(f[i-1][j]+f[i][j-1])*1ll*inv2%mod;
}
}
int ans=0;
for(int rt=1;rt<=n;rt++){
for(int i=1;i<=n;i++){
dep[i]=top[i]=hes[i]=sz[i]=fa[i]=0;
}
dfs1(rt),dfs2(rt);
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
int tmp=lca(i,j);
(ans+=f[dep[i]-dep[tmp]][dep[j]-dep[tmp]])%=mod;
}
}
}
printf("%lld",ans*1ll*qpow(n,mod-2)%mod);
return 0;
}
}
int main(){return asbt::main();}
浙公網安備 33010602011771號