CF1249F Maximum Weight Subset

一、题目

点此看题

二、解法

设 $dp[u][i]$表示以 $u$为根的子树，选出的点最小深度大于等于 $i$（这里深度指相对于子树根的深度），且两两距离大于等于 $k$的方案数（本文的 $k$自动 $+1$），其实这种套路很常见了（我记得 $online3$有一道题也是如此），把状态定义成一段区间（这里指大于等于 $i$），方便转移和算答案，并且对正确性也没有什么影响，转移：

• 以前的子树选深度大于等于 $i$，当前子树必须大于等于 $\max(i,k-i)$（距离大于等于 $k$）： $dp[u][i]+dp[v][\max(i,k-i)-1]$
• 当前的子树选深度大于等于 $i$，以前子树必须大于等于 $\max(i,k-i)$： $dp[u][\max(i,k-i)]+dp[v][i-1]$

这样做 $O(n^2)$

#include <cstdio>
#include <iostream>
using namespace std;
const int M = 205;
int read()
{int x=0,flag=1;char c;while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return x*flag;
}
int n,k,tot,f[M],a[M],dp[M][M];
struct edge
{int v,next;
}e[2*M];
void dfs(int u,int fa)
{dp[u][0]=a[u];for(int i=f[u];i;i=e[i].next){int v=e[i].v;if(v==fa) continue;dfs(v,u);for(int j=0;j<=n;j++){if(j==0){dp[u][j]=dp[u][j]+dp[v][max(j,k-j)-1];continue;}dp[u][j]=max(dp[u][j]+dp[v][max(j,k-j)-1],dp[u][max(j,k-j)]+dp[v][j-1]);}}for(int i=n;i>=0;i--)dp[u][i]=max(dp[u][i],dp[u][i+1]);
}
signed main()
{n=read();k=read()+1;for(int i=1;i<=n;i++)a[i]=read();for(int i=1;i<n;i++){int u=read(),v=read();e[++tot]=edge{v,f[u]},f[u]=tot;e[++tot]=edge{u,f[v]},f[v]=tot;}dfs(1,0);printf("%d\n",dp[1][0]);
}