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

hwh_qwq · 2025-05-03 09:57:48 · 题解

因为小蓝每步可以走最多 2 条边，每次可以走最多 k 步，所以他最多只能走到距离根节点不超过 2 \times k 的点，即深度不超过 2 \times k + 1 的点。

对于每个深度 \le 2 \times k+1 的点，我们可以先走 \lfloor \text{深度}\div2 \rfloor 步，每步走两条边，如果深度为偶数，再走一步即可。

通过上面这样的走法，所有深度不超过 2 \times k + 1 的点都可以在 k 步之内到达，又因为寻宝的次数没有限制，所以我们可以获得这些点上的所有物品，答案即为深度不超过 2 \times k + 1 的点 i 的 w_i 之和。

一些需要注意的地方：

• 存图的时候记得双向存边。
• 根节点的价值也要算入答案。
• 答案可能会超过 int 的范围，要开 long long。

代码：

#include<iostream>
#include<vector>
using namespace std;
int n,k;
int w[100005],deep[100005],vis[100005];
vector<int> tr[100005];
void dfs(int id,int fa,int dep){
    if(vis[id]==1) return;
    vis[id]=1;
    deep[id]=dep;
    for(int i=0;i<tr[id].size();i++){
        if(tr[id][i]!=fa) dfs(tr[id][i],id,dep+1);
    }
}
int main(){
    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;
        tr[u].push_back(v);
        tr[v].push_back(u);
    }
    dfs(1,0,0);
    long long ans=0;
    for(int i=1;i<=n;i++){
        if(deep[i]<=2*k) ans+=w[i];
    }
    cout<<ans;
    return 0;
}