本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
说我们IIS7站长博客，有一篇博文用了他们的图片。
要求我们给他们一张图片6000元。要不然法院告我们
为避免不必要的麻烦，IIS7站长博客，全站内容图片下架、并积极应诉
博文内容全部不再显示，请需要相关资讯的站长朋友到必应搜索。谢谢！
另祝：版权碰瓷诈骗团伙，早日弃暗投明。
相关新闻：借版权之名、行诈骗之实，周某因犯诈骗罪被判处有期徒刑十一年六个月
叹！百花齐放的时代,渐行渐远!
这道题的状态可以设计为f[i][j]表示在以i为根的子树上，深度最小为j的最大值。这个深度是相对于子树的深度
因此我们枚举深度去更新当前子树答案，在第一次更新的时候，先去求深度恰好为j的答案，之后倒序取一遍max就是答案
如果深度为0，就是选择根节点，那么只要把所有子树中>=k的位置选进来就行（这里的k已经先行+1）
如果深度不为0，那么我们就去枚举子树，表示深度为j的点在哪个子树上。但是在这个更新中，其实我们求取的并不一定就是物理意义为深度恰好为j，但这并不影响答案
，之后只需要对其他子树枚举距离大于等于k并且深度不超过j的答案叠加即可，可能有人会有疑惑说其他子树之前是否会距离不足k，这是显然不可能的，因为我们有max约束，具体可以看代码领会
因为我们枚举了深度为j的在哪个子树，所以我们枚举完了所有的答案
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const int N=2e5+10;
int a[N];
vector<int> g[N];
int h[N],e[N],ne[N],idx;
int f[500][500];
int n,k;
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int fa){
int i;
for(i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(j==fa)
continue;
dfs(j,u);
}
for(i=0;i<201;i++){
if(i==0){
f[u][0]=a[u];
for(int j=h[u];j!=-1;j=ne[j]){
int v=e[j];
if(v==fa)
continue;
f[u][0]+=f[v][max(0,k-1)];
}
}
else{
for(int j=h[u];j!=-1;j=ne[j]){
int v=e[j];
if(v==fa)
continue;
int dis=f[v][i-1];
for(int x=h[u];x!=-1;x=ne[x]){
int d=e[x];
if(d==v||d==fa)
continue;
dis+=f[d][max(i-1,k-i-1)];
}
f[u][i]=max(f[u][i],dis);
}
}
}
for(i=201;i>=0;i--)
f[u][i]=max(f[u][i+1],f[u][i]);
}
int main(){
ios::sync_with_stdio(false);
int i,j;
cin>>n>>k;
k++;
memset(h,-1,sizeof h);
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<n;i++){
int u,v;
cin>>u>>v;
add(u,v);
add(v,u);
}
dfs(1,-1);
cout<<f[1][0]<<endl;
return 0;
}
View Code
