题解：P11378 [GESP202412 七级] 燃烧

Leathback · 2024-12-12 20:09:27 · 题解

这道题算是比较水的。虽然题目里说的是树，但其实就是一个无向图。虽然赛后增加了难度，但加一个记忆化就行了。

题意

给你一个有 n 个节点，n-1 条边的无向图，每个节点都有一个权值 a_i。当节点 i 与节点 j 直接联通且满足 a_i > a_j 时，节点 i 就会引燃节点 j。求在合理选择初始节点的情况下，最多可以燃烧多少个节点。

思路

考虑使用循环枚举初始节点，再用 dfs 遍历图计算可以引燃的节点，再将这些答案取最大值即可。注意要用记忆化。

给出代码：

#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+5;
int n;
int a[N];
int dp[N];//记忆化数组 
vector<int>g[N];//使用邻接表储存图
int dfs(int k)//k指当前节点 
{
    if(dp[k])return dp[k];//如果计算过就返回 
    dp[k]=1;//点燃自己 
    for(int i:g[k])//遍历能到达的节点 
        if(a[k]>a[i])//如果符合要求 
            dp[k]+=dfs(i);//加上结果 
    return dp[k];
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
        //建图 
    } 
    //以上是输入
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,dfs(i));//取最大值
    printf("%d\n",ans);
    return 0;
}