题解：P11378 [GESP202412 七级] 燃烧

· · 题解

题目描述

在一个有 N 节点的树内，以随机一个点为根的树共有几个权值比它小的子节点。

知识点提炼

记忆化搜索。

思路

我们发现这道题有 10^5 的数据范围，首先想到的是 O(n) 的时间复杂度，本蒟蒻考场上只能想到深搜，可是必须使用记忆化，保证所有节点只访问一次，减少冗余运算：

搜出所有比原点小的儿子，统计满足条件的儿子数量再将其回溯到父亲节点。如果访问过了该节点，直接将已经统计完的数据返回自己的父亲。

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int n,a[1000006],vis[1000006];
vector<int> edge[1000006];
int dfs(int x){
    if(vis[x] != 0) return vis[x];
    //如果访问过了，直接返回之前的值，保证每个节点访问一次。 
    int cnt = 0;
    for(auto &v : edge[x])
        if(a[x] > a[v]) //如果连接的点比自己的小 
            cnt += dfs(v); //先统计 
    return vis[x] = cnt + 1;
    //这里的 1 是自己，因为自己属于节点，所以+1 
}
main(){
    cin >> n;
    for(int i = 1;i <= n; i++) cin >> a[i];
    for(int i = 1,x,y;i < n; i++){
        cin >> x >> y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    int ans = 0;
    for(int i = 1;i <= n; i++)
        ans = max(ans,dfs(i));
    //直接取最大值，不一定是节点1之类的 
    cout << ans;
}

~蒟蒻的第一篇题解，求过求过求过~