题解：P12343 [蓝桥杯 2025 省 AB/Python B 第二场] 树上寻宝

· · 题解

思路

题目说小蓝最多走 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;
}