G7010 [GESP202412 七级] 燃烧 题解

知识点：树上动态规划、拓扑顺序、排序。

解题思路

按节点数值升序处理，dp[u]初值1，累加所有相邻且值严格更小的节点的dp，最大dp就是最好点火位置。

为什么正确

火沿数值严格下降传播，树上各相邻方向的可达子树互不相交；较小节点先计算保证可累加其完整规模。

易错点

相等值之间不传播；树的无环性保证不同邻接分支不会被重复计数。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>a(n+1),dp(n+1,1),order;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        order.push_back(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);
    }
    sort(order.begin(),order.end(),[&](int u,int v){return a[u]<a[v];});
    int ans=1;
    for(int u:order) {
        for(int v:g[u])if(a[v]<a[u])dp[u]+=dp[v];
        ans=max(ans,dp[u]);
    }
    cout<<ans;
}

说明

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