题解：P11378 [GESP202412 七级] 燃烧

Undefined_Shawn · 2024-12-11 21:29:17 · 题解

解题思路

这道题可以把树看做一个图。我们可以从每个点开始， dfs 搜索相邻的节点。对每个点出发搜到的点的个数取最大值。

这道题代码如下：（现在没拿到代码，重写了一份）

using namespace std;

vector<int> v[100005];
int c[100005], vis[100005], maxn = -1, n;

int dfs(int u) {
    if (vis[u]) return vis[u];
    int cnt = 1;
    for (int i : v[u])
        if (c[i] < c[u])
            cnt += dfs(i);
    vis[u] = cnt;
    return cnt;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) {
        maxn = max(maxn, dfs(i));
    }
    cout << maxn;
    return 0;
}