Nadajniki
有一个妙妙树形 DP。
设 \(f_{i,0/1/2,0/1/2,0/1/2}\) 为第 \(i\) 个点，这个点上放没放，他儿子有没有放，他父亲有没有放。
然后硬转移就行了。
f[p][0][0][1]=f[p][0][0][2]=f[p][0][0][0]=0;
f[p][1][0][0]=1;f[p][2][0][0]=2;
for(int i=head[p];i;i=nxt[i])
{
int v=to[i];
if(v==fa) continue;
dfs(to[i],p);
long long mn=inf;
for(int j=0;j<=2;j++)
for(int k=0;k<=2;k++)
for(int l=0;l<=2;l++)
mn=min(mn,f[v][j][k][l]),g[j][k][l]=f[p][j][k][l];
f[p][2][0][0]+=mn;mn=inf;
for(int j=0;j<=2;j++)
for(int k=0;k<=2;k++)
for(int l=0;l<=1;l++)
mn=min(mn,f[v][j][k][l]);
f[p][1][0][0]+=mn;
f[p][0][0][0]+=f[v][0][2][0];
f[p][0][0][1]+=min(f[v][0][2][0],f[v][0][1][0]);
f[p][0][0][2]+=min({f[v][0][2][0],f[v][0][1][0],f[v][0][0][0]});
for(int j=0;j<=2;j++)
f[p][0][1][j]=min(g[0][1][j]+min({f[v][0][2][0],f[v][0][1][0],j>0?f[v][0][0][0]:inf}),g[0][0][min(j+1,2)]+f[v][1][0][0]);
for(int j=0;j<=2;j++)
f[p][0][2][j]=min({g[0][2][j]+min({f[v][0][2][0],f[v][0][1][0],f[v][0][0][0],f[v][1][0][0],f[v][2][0][0]}),g[0][1][min(j+1,2)]+min(f[v][2][0][0],f[v][1][0][0]),g[0][0][2]+f[v][2][0][0]});
}
后记
卡哇伊内
标签：有没有,卡哇伊,int,POI2016,long,inf From： https://www.cnblogs.com/cc0000/p/16790051.html