题目链接
题目思路
设\(dp[i][j]\)表示和\(i\)的子数中和\(i\)距离距离最近的点的长度为\(j\)的答案
然后胡乱转移
对于这种要考虑多个子树的问题要多考虑
代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=2e2+5,inf=0x3f3f3f3f,mod=1000;
const double eps=1e-6;
int n,k;
int a[maxn];
int dp[maxn][maxn];
vector<int> g[maxn];
void dfs(int u,int fa){
dp[u][0]=a[u];
for(auto i:g[u]){
if(i==fa) continue;
dfs(i,u);
dp[u][0]+=dp[i][k];
}
for(int dep=1;dep<=n;dep++){
for(auto i:g[u]){
if(i==fa) continue;
int sum=dp[i][dep-1];
for(auto j:g[u]){
if(j==fa||j==i) continue;
sum+=dp[j][max(dep-1,k-dep)];
}
dp[u][dep]=max(dp[u][dep],sum);
}
}
for(int i=n;i>=0;i--){
dp[u][i]=max(dp[u][i+1],dp[u][i]);
}
}
signed main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1,u,v;i<=n-1;i++){
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,1);
printf("%d\n",dp[1][0]);
return 0;
}