自动搬运

查看原文

来自洛谷，原作者为

	Clare613 csacademy.com||宣:https://www.luogu.com.cn/team/103922||250粉后橙名就别找我了||目标一：黄+绿+蓝+紫+黑->431/888||目标二：2025J：320+，2025S:250+||个人题库已满

搬运于2025-08-24 23:14:47，当前版本为作者最后更新于2025-04-26 22:48:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

题目说小蓝最多走 $k$ 步，每一步可以跨过 $1$ 条边或 $2$ 条边，翻译成人话就是可以得到深度不大于 $2k + 1$ 的点权，于是我们只要求出每个点的深度，点权加起来输出即可。
肯定有人不会求树的深度，我们可以用 DFS 来找，建一下边，从一开始跑，不断加就可以求出树的深度了！

code:

#include<bits/stdc++.h>
#define int long long
#define MOD 1000000007
using namespace std;
vector<int> g[100005];
int shen[100005],w[100005],ans;
void dfs(int x,int fa){
	for(auto i:g[x]){
		if(i==fa) continue;
		shen[i]=shen[x]+1;
		dfs(i,x);
	}
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
		cin>>w[i];
	}
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	shen[1]=1;
	dfs(1,0);
	for(int i=1;i<=n;i++){
		if(shen[i]<=2*k+1) ans+=w[i];
	}
	cout<<ans;
	return 0;
}