E1. 游戏（简单版） 详细题解

题目理解

有一棵以 $1$ 为根的树，每个节点 $i$ 有权值 $w_i$。两人轮流操作，Cirno 先手。
每轮操作：假设上一轮对手选了节点 $j$（第一轮无限制），当前玩家必须选一个未被删除的节点 $i$，满足 $w_i > w_j$，然后删除节点 $i$ 的整个子树（包括 $i$ 自己）。
无法操作的玩家获胜。双方都采取最优策略。
要求：如果 Cirno 有必胜策略，输出她第一回合可能选择的任意一个节点；否则输出 $0$。

关键结论

Cirno 第一步选节点 $i$ 能够获胜 当且仅当 在树中（删除 $i$ 的子树之前）存在至少一个节点 $j$，使得：

• $j$ 不在 $i$ 的子树内；
• $w_j > w_i$。

换句话说，$i$ 的子树之外的最大权值必须严格大于 $w_i$。

为什么这个条件正确？

1. 如果子树外不存在更大权值的节点
   那么 Cirno 选 $i$ 之后，剩下的所有节点权值都 $\le w_i$。由于下一轮 Daiyousei 必须选一个权值 $> w_i$ 的节点，她无法操作。根据规则，“第一个无法操作的玩家获胜”，所以 Daiyousei 获胜，Cirno 输。
   因此这样的 $i$ 不可取。

2. 如果子树外存在更大权值的节点
   设 $M$ 为所有节点权值的最大值。考虑从大到小归纳：

   • 权值最大的节点（等于 $M$）必败：因为选了它之后对手无法操作，对手获胜。
   • 对于权值为 $M-1$ 的节点，如果它的子树外存在权值为 $M$ 的节点，那么对手只能选那个 $M$（因为只有 $> M-1$ 的节点可选），而选 $M$ 是败招，所以对手输，当前玩家赢。如果不存在，则对手无步可走，对手赢，当前玩家输。
   • 依此类推，一个节点 $i$ 是必胜态，当且仅当存在一个不在其子树内且权值更大的节点是必败态。
     可以证明，这个条件等价于“子树外存在任意一个权值更大的节点”。因为从全局最大权值开始，所有“子树外更大”的节点会通过归纳传递必胜态。

因此，只要 $i$ 的子树外有任何一个权值大于 $w_i$ 的节点，Cirno 第一步选 $i$ 就必胜。

算法实现

1. 对树做一次 DFS，求出每个节点的：
   • $dfn[i]$：DFS 序（进入时间戳，$1$ 到 $n$）
   • $low[i]$：以 $i$ 为根的子树中最大的 DFS 序（即子树区间 $[dfn[i], low[i]]$）
2. 构造一个数组 $nfd[x]$，表示 DFS 序为 $x$ 的节点编号。
3. 预处理前缀最大值 $pre[x] = \max\{w_{nfd[1]}, ..., w_{nfd[x]}\}$ 和后缀最大值 $suf[x] = \max\{w_{nfd[x]}, ..., w_{nfd[n]}\}$。
4. 对于每个节点 $i$：
   • 它的子树之外对应的 DFS 序区间为 $[1, dfn[i]-1]$ 和 $[low[i]+1, n]$。
   • 子树外的最大权值 = $\max(pre[dfn[i]-1],\; suf[low[i]+1])$（边界情况视为 $0$）。
   • 如果这个值 $> w_i$，则 $i$ 是一个可行的第一步选择。
5. 输出任意一个满足条件的节点（代码中输出权值最大的那个），如果没有则输出 $0$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

代码实现（C++）

#include "bits/stdc++.h"
using namespace std;
const int N = 1e6 + 5;
vector<int> e[N];
int w[N], dfn[N], nfd[N], pre[N], suf[N], low[N];
bool ed[N];
int id;

void dfs(int u) {
    if (ed[u]) return;
    ed[u] = 1;
    dfn[u] = ++id;
    nfd[id] = u;
    for (int v : e[u]) dfs(v);
    ed[u] = 0;
    low[u] = id;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        for (int i = 1; i <= n; i++) {
            e[i].clear();
            id = 0;
        }
        for (int i = 1; i <= n; i++) cin >> w[i];
        for (int i = 1; i < n; i++) {
            int u, v; cin >> u >> v;
            e[u].push_back(v);
            e[v].push_back(u);
        }
        dfs(1);
        for (int i = 1; i <= n; i++)
            pre[i] = max(pre[i-1], w[nfd[i]]);
        suf[n+1] = 0;
        for (int i = n; i >= 1; i--)
            suf[i] = max(suf[i+1], w[nfd[i]]);
        int mx = 0;
        for (int i = 1; i <= n; i++) {
            int outside = max(pre[dfn[i]-1], suf[low[i]+1]);
            if (outside > w[i] && w[i] > w[mx])
                mx = i;
        }
        cout << mx << '\n';
    }
    return 0;
}