[C++] P11378 [GESP202412 七级] 燃烧

发表于 分类于

小杨有一棵包含 n 个节点的树，其中节点的编号从 1 到 n。节点 i 的权值为 ai。

小杨可以选择一个初始节点引燃，每个燃烧的节点会将其相邻节点中权值严格小于自身权值的在节点间扩散直到不会有新的节点被引燃。

小杨想知道在合理选择初始节点的情况下，最多可以燃烧多少个节点。

输入格式

第一行包含一个正整数 n，表示节点数量。

第二行包含 n 个正整数 a1, a2, …, an，代表节点权值。

之后 n − 1 行，每行包含两个正整数 ui, vi，代表存在一条连接节点 ui 和 vi 的边。

输出格式

输出一个正整数，代表最多燃烧的节点个数。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
5
6 2 3 4 5
1 2
2 3
2 5
1 4

输出 #1

1
3

说明/提示

子任务编号 数据点占比 n
1 20%  ≤ 10
2 20%  ≤ 100
3 60%  ≤ 105

对于全部数据，保证有 1 ≤ n ≤ 105，1 ≤ ai ≤ 106。

题解

带条件的图遍历而已，甚至因为严格小都不需要标记了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

int f(vector<int> m[], int c, int p[], int a[]){
    if(a[c]) return a[c];
    a[c] = 1;
    for(int t : m[c])
        if(p[t]<p[c])
            a[c] += f(m, t, p, a);
    return a[c];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    int *p = new int[n];
    for(int i=0;i<n;i++) cin >> p[i];

    vector<int> *m = new vector<int>[n];
    for(int i=1;i<n;i++){
        int u, v;
        cin >> u >> v;
        u--; v--;
        m[u].push_back(v);
        m[v].push_back(u);
    }

    int *a = new int[n];
    memset(a, 0, sizeof(int)*n);
    int x = 0;
    for(int i=0;i<n;i++) x = max(x, f(m, i, p, a));

    cout << x;
    
    return 0;
}