这题得看数据范围评难度，如果\(n\)出到\(2e6\)感觉可以有个\(2600\)？

首先我们一眼便可得出一个\(O(n^2)\)的\(dp\)

设\(f[x][i]\)表示，在以\(x\)为根的子树内，离\(x\)最近的选择了的点的距离为\(i\)时的最大价值

则转移很显然，直接合并子树信息即可

注意到\(i\)的范围在\(siz[x]\)内，则复杂度为\(O(n^2)\)

code

#include 
#define rep(a,b,c) for(int a=(b);a<=(c);a++)
#define per(a,b,c) for(int a=(b);a>=(c);a--)
#define repe(a) for(int yny=head[a],v;yny&&(v=e[yny].v);yny=e[yny].u)
using namespace std;
struct Edge {
	int u,v;
}e[401];
int head[201],ecnt;
inline void adde(int u,int v) { e[++ecnt].v=v;e[ecnt].u=head[u];head[u]=ecnt; }
inline void add(int u,int v) { adde(u,v); adde(v,u); }
int f[201][201],g[201];
int n,k,a[201],A,B,ans,siz[201];
inline void dfs(int x,int fa) {
	f[x][0]=a[x]; siz[x]=1;
	repe(x) if(v!=fa) {
		dfs(v,x);
		memset(g,0,sizeof(g));
		rep(i,0,max(siz[x],siz[v])) rep(j,0,siz[v]) if((i+j+1)>k) g[min(i,j+1)]=max(g[min(i,j+1)],f[x][i]+f[v][j]);
		rep(i,0,siz[x]+siz[v]) f[x][i]=g[i];
		siz[x]+=siz[v];
	}
}
inline void solve() {
	scanf("%d %d",&n,&k);
	rep(i,1,n) scanf("%d",&a[i]);
	rep(i,2,n) {
		scanf("%d %d",&A,&B);
		add(A,B);
	}
	dfs(1,0);
	rep(i,0,n) ans=max(ans,f[1][i]);
	printf("%d\n",ans);
}
int main() {
	//int T; cin>>T; while(T--)
	solve();
}

对\(O(n)\)做法，我们要重新将状态定义为\(f[x][i]\)表示，选择了的点离\(x\)最近的距离至少为\(i\)的最大价值

我们考虑合并两个\(f\)数组的时候将长度小的往大的上合并

设长度大的为\(f\)，长度小的为\(g\)

那么\(g\)能改变的就是\(g\)的长度那一段的值

又考虑将它们合并后相当于\(g\)中的所有元素都被删掉了，而每个元素最多会被删一次，所以复杂度是\(O(n)\)

code

//对我就是学的Kelin大佬
#include 
#define rep(a,b,c) for(int a=(b);a<=(c);a++)
#define per(a,b,c) for(int a=(b);a>=(c);a--)
#define repe(a) for(int yny=head[a],v;yny&&(v=e[yny].v);yny=e[yny].u)
using namespace std;
struct Edge {
	int u,v;
}e[401];
int head[201],ecnt;
inline void adde(int u,int v) { e[++ecnt].v=v;e[ecnt].u=head[u];head[u]=ecnt; }
inline void add(int u,int v) { adde(u,v); adde(v,u); }
int n,k,A,B,a[201];
inline void merge(deque &f,deque &g) {
	if(f.size() tmp=vector{g.begin(),g.end()};
	rep(i,0,g.size()-1) {
		int res=max(i,k-i);
		if(res dfs(int x,int fa) {
	deque nf={a[x]};
	repe(x) if(v!=fa) {
		deque ng=dfs(v,x);
		ng.push_front(ng.front());
		merge(nf,ng);
	}
	return nf;
}
inline void solve() {
	scanf("%d %d",&n,&k); k++;
	rep(i,1,n) scanf("%d",&a[i]);
	rep(i,2,n) {
		scanf("%d %d",&A,&B);
		add(A,B);
	}
	printf("%d\n",dfs(1,0).front());
}
int main() {
	//int T; cin>>T; while(T--)
	solve();
}