G8009 [GESP202412 八级] 树上移动 题解

知识点：树遍历、路径枚举、约束剪枝。

解题思路

从每个起点遍历整棵树，记录路径累计代价b与节点数len，代价超过k则剪枝，否则更新最大长度并向未访问父亲以外的邻点延伸。

为什么正确

树中任意起终点间路径唯一，枚举所有起点与后续树路径覆盖全部候选；代价非负使超限后不可能重新可行。

易错点

当前起点自身代价也要计入；剪枝依赖题目代价非负，不能推广到负代价树。

复杂度

最坏时间O(n²)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    vector<vector<int>>g(n+1);
    for(int i=1;i<n;i++) {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int ans=0;
    for(int s=1;s<=n;s++) {
        vector<array<int,4>>q= {
            {
                s,0,a[s],1
            }
        }
        ;
        for(int z=0;z<(int)q.size();z++) {
            auto [u,p,b,len]=q[z];
            if(b>k)continue;
            ans=max(ans,len);
            for(int v:g[u])if(v!=p)q.push_back({v,u,b+a[v],len+1});
        }
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。