算法竞赛模板

E1. The Game (Easy Version)

题意 ： 博弈，给定一颗树，树根为1， 树的节点有权值

只能按照递增顺序选择一个节点然后删除以该节点为根的子树

不能操作的人赢

求先手胜的一个可能选点，先手没法胜就输出0

那就找一个节点，除了它的子树以外只有一个节点比它大，那就必胜

可以用dfs序快速确立一个子树的节点的范围

然后查询其他节点（即另外两个区间）的最大值，用dfs序的前后缀数组维护即可

枚举求最大的满足条件的节点

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll

void solve() {
    int n;
    cin >> n;
    vector<int> v(n + 1);
    vector<int> head(n + 1), to(2 * n + 10), nx(2 * n + 10);
    int id = 1;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    auto ad = [&](int x, int y) {
        to[id] = y;
        nx[id] = head[x];
        head[x] = id++;
    };
    for (int i = 1; i <= n - 1; i++) {
        int x1, y1;
        cin >> x1 >> y1;
        ad(x1, y1);
        ad(y1, x1);
    }
    vector<int> in(2*n+2), out(2*n+2), r(2*n+2);
    int ts = 1;
    auto dfs = [&](auto&& self, int cur, int f) -> void {
        r[ts] = cur;
        in[cur] = ts++;
        for (int i = head[cur]; i; i = nx[i]) {
            if (to[i] == f) continue;
            self(self, to[i], cur);
        }
        out[cur] = ts-1;
    };
    dfs(dfs, 1, -1);
    vector<int> pre(2*n+2), suf(2*n+2);
    for (int i = 1; i <= n; i++) {
        pre[i] = max(pre[i-1],v[r[i]]);
    }
    for (int i = n; i > 0; i--) {
        suf[i] = max(suf[i+1],v[r[i]]);
    }
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        if (max(pre[in[i]-1],suf[out[i]+1]) > v[i] && v[i] > v[mx]) {
            mx = i;
        }
    }
    cout << mx << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}