E2. 游戏（困难版）详细题解

问题重述

给定一棵以 $1$ 为根的有根树，每个节点 $i$ 有一个权值 $w_i$。两人轮流操作，Cirno 先手。每轮操作：假设上一轮对手选了节点 $j$（第一轮无限制），当前玩家必须选择一个未被删除的节点 $i$，满足 $w_i > w_j$，然后删除节点 $i$ 的整棵子树（包括 $i$ 本身）。无法操作的玩家获胜。双方都采取最优策略。对于每个测试用例，输出 Cirno 在第一回合可以选择的所有节点（按升序）；若不存在则输出 $0$。

博弈分析

设 $M = \max\{w_i\}$。

• 若当前玩家选择了一个权值为 $M$ 的节点，则对手无法操作，对手获胜 → 选权值为 $M$ 的节点是必败的。
• 考虑权值为 $M-1$ 的节点 $u$。
  如果 $u$ 的子树外存在权值为 $M$ 的节点 $v$，那么选 $u$ 后对手只能选 $v$，而选 $v$ 是必败态，因此 $u$ 是必胜态。
  如果 $u$ 的子树内包含了所有权值为 $M$ 的节点，则选 $u$ 后所有 $M$ 节点被删除，对手无合法操作，对手获胜 → $u$ 是必败态。
• 依此类推，对于任意节点 $i$，定义 $S = \{j \mid w_j > w_i\}$。
  若 $S$ 中存在至少一个节点不在 $i$ 的子树内，则选 $i$ 后对手必须从 $S$ 中选择一个节点，而所有 $S$ 中的节点（因为权值更大）都是必败态，因此对手必败 → $i$ 是必胜态。
  若 $S$ 中所有节点都在 $i$ 的子树内，则选 $i$ 后 $S$ 被全部删除，对手无步可走，对手获胜 → $i$ 是必败态。

核心结论：节点 $i$ 是 Cirno 第一步必胜选择 当且仅当 在 $i$ 的子树外存在至少一个节点 $j$ 满足 $w_j > w_i$。

转化为树上区间查询

对树进行 DFS，得到每个节点的 DFS 序 $dfn[i]$ 和其子树内最大的 DFS 序 $low[i]$。节点 $i$ 的子树对应连续区间 $[dfn[i], low[i]]$。子树外的节点对应两个区间：$[1, dfn[i]-1]$ 和 $[low[i]+1, n]$。

定义数组 $nfd[x]$ 表示 DFS 序为 $x$ 的节点编号。预处理：

• 前缀最大值 $pre[x] = \max\{w_{nfd[1]}, w_{nfd[2]}, \dots, w_{nfd[x]}\}$，并令 $pre[0]=0$。
• 后缀最大值 $suf[x] = \max\{w_{nfd[x]}, w_{nfd[x+1]}, \dots, w_{nfd[n]}\}$，并令 $suf[n+1]=0$。

对于节点 $i$，子树外的最大权值为：

$$out = \max\big(pre[dfn[i]-1],\; suf[low[i]+1]\big) $$

判断条件为：$out > w_i$。

算法步骤

1. 读入 $t$ 组测试数据。
2. 对每组数据：
   a. 读入 $n$ 和权值 $w[1..n]$。
   b. 建图（无向边）。
   c. 从根 $1$ 开始 DFS，记录 $dfn$、$low$ 和 $nfd$ 数组。
   d. 计算前缀最大值数组 $pre[0..n]$。
   e. 计算后缀最大值数组 $suf[1..n+1]$。
   f. 遍历所有节点 $i$（$1 \le i \le n$）：
   计算 $out = \max(pre[dfn[i]-1], suf[low[i]+1])$。
   如果 $out > w[i]$，则将 $i$ 加入答案集合。
   g. 将答案集合排序后输出：先输出个数 $k$，再按升序输出所有节点。如果答案集合为空，输出 $0$。

复杂度分析

• DFS 遍历：$O(n)$。
• 预处理前缀/后缀：$O(n)$。
• 遍历判断：$O(n)$。
• 排序答案：$O(k \log k)$，其中 $k$ 为答案个数，$k \le n$。
• 总复杂度：$O(n \log n)$，实际 $n$ 总和不超过 $4 \times 10^5$，完全可行。
• 空间复杂度：$O(n)$。

代码实现（C++）

#include <bits/stdc++.h>
using namespace std;

const int N = 4e5 + 10;
vector<int> e[N];
int w[N], dfn[N], nfd[N], low[N], pre[N], suf[N];
int n, id;

void dfs(int u, int fa) {
    dfn[u] = ++id;
    nfd[id] = u;
    for (int v : e[u]) {
        if (v == fa) continue;
        dfs(v, u);
    }
    low[u] = id;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> w[i];
        e[i].clear();
    }
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    id = 0;
    dfs(1, 0);
    pre[0] = 0;
    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]]);
    }
    vector<int> ans;
    for (int i = 1; i <= n; ++i) {
        int outside = max(pre[dfn[i]-1], suf[low[i]+1]);
        if (outside > w[i]) {
            ans.push_back(i);
        }
    }
    sort(ans.begin(), ans.end());
    if (ans.empty()) {
        cout << "0\n";
    } else {
        cout << ans.size();
        for (int x : ans) cout << ' ' << x;
        cout << '\n';
    }
}

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