codeforces1249F Maximum Weight Subset

题目链接：cf

这里介绍的是(O(n^3))的dp做法

记(f_{u,i})表示在(u)为根的子树中，所有选择的点与(u)的距离至少为(i)的最大点权和

(i=0)时，也就是必须选(u)，剩下的就是它的所有儿子(v)中的(f_{v,k})

(i>0)时，我们枚举(dis)的最小点所在的子树(v)，由枚举知道这棵子树对答案的贡献为(f_{v,i-1})，之后考虑剩余的子树（记根为(w)），由于这之中的点不会比(v)子树中的选取点更浅的点，所以它们到根(w)的(dis)一定(geq w-1)，在加上任意两点之间距离至少为(k+1)，故子树(w)的贡献为(f_{w,max(k-i,i-1)})。最后对所有(v)的答案取(max)。

还要注意到的是我们需要对上面求出来的(f)求一个后缀max，这个根据状态的定义十分的显然

最后的答案就是(f_{1,0})

 #include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
struct node{int to,nxt;}sq[420];
int all=0,head[220];
int n,lim,a[220],f[220][220];

int read()
{
    int x=0,f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

void add(int u,int v)
{
	all++;sq[all].to=v;sq[all].nxt=head[u];head[u]=all;
}

void dfs(int u,int fu)
{
	for (int i=head[u];i;i=sq[i].nxt)
	{
		int v=sq[i].to;
		if (v==fu) continue;
		dfs(v,u);
	}
	rep(j,0,lim)
	{
		if (j==0)
		{
			f[u][0]=a[u];
			for (int i=head[u];i;i=sq[i].nxt)
			{
				int v=sq[i].to;
				if (v!=fu) f[u][0]+=f[v][lim];
			}
		}
		else
		{
			for (int i=head[u];i;i=sq[i].nxt)
			{
				int v=sq[i].to,now=f[v][j-1];
				if (v==fu) continue;
				for (int k=head[u];k;k=sq[k].nxt)
				{
					int w=sq[k].to;
					if ((v==w) || (fu==w)) continue;
					now+=f[w][max(lim-j,j-1)];
				}
				f[u][j]=max(f[u][j],now);
			}
		}
	}
	per(i,lim,0) f[u][i]=max(f[u][i],f[u][i+1]);
}

int main()
{
	n=read();lim=read();
	rep(i,1,n) a[i]=read();
	rep(i,1,n-1)
	{
		int u=read(),v=read();
		add(u,v);add(v,u);
	}
	dfs(1,0);
	printf("%d",f[1][0]);
	return 0;
}