这是我 OI 生涯里见过的最难的黄题。
# 问题描述
给定一棵有根二叉树，包含 $2n-1$ 个节点，其中 $n$ 个叶子，每个叶子有一个真假值（True/False），每个非叶子点有一个运算符（AND 或 OR）。黑恶势力（以下简称黑）按照一个固定顺序 $p_i$ 询问叶子的值，但这个~~人工智能~~人会跳过不必要的询问（即当结果已确定时）。你需要：
1. 为每个叶子分配真假值，使得黑的询问次数尽到达最大值。
2. 在询问次数最多的前提下，使根节点的值为 True。
# 问题分析
1. 懒一点
1. AND 节点：当左子树为 False 时，不需要询问右子树。
2. OR 节点：当左子树为 True 时，不需要询问右子树。
2. 定义询问的次数：
1. 对于叶子，询问次数就是它在序列中的索引。
2. 对于非叶子点，询问次数取决于它子树的求值顺序和短路规则。
3. 防止 TLE：
1. 最大化整棵树的最终确定时间。
2. 在多个方案都能达到最大确定时间时，选择根为 True 的结果。
# 算法思路
对于每个节点 $u$，我们需要维护两个值：
## DP 法则
1. $f_u(0)$：以 $u$ 为根的子树，当 $u$ 的值为 False 时的最大确定时间。
2. $f_u(1)$：以 $u$ 为根的子树，当 $u$ 的值为 True 时的最大确定时间。
## 状态转移方程
设 $u$ 的两个子节点为 $a$ 和 $b$：
### 情况 1：$u$ 是 AND 节点
1. 当 $u = \text{False}$ 时：
- 情况 A：$a = \text{False}$，$b$ 任意。
- 确定时间 = $\min(f_a(0), \text{位置}(b))$（取较早判刑的一个）。
- 情况 B：$a = \text{True}$，$b = \text{False}$。
- 确定时间 = $f_b(0)$。
2. 当 $u = \text{True}$ 时：
- 必须 $a = \text{True}$ 且 $b = \text{True}$。
- 确定时间 = $\max(f_a(1), f_b(1))$（需要两个都为真才能确定）。
### 情况 2：$u$ 是 OR 节点
1. 当 $u = \text{False}$ 时：
- 必须 $a = \text{False}$ 且 $b = \text{False}$。
- 确定时间 = $\max(f_a(0), f_b(0))$。
2. 当 $u = \text{True}$ 时：
- 情况 A：$a = \text{True}$，$b$ 任意。
- 确定时间 = $\min(f_a(1), \text{位置}(b))$。
- 情况 B：$a = \text{False}$，$b = \text{True}$。
- 确定时间 = $f_b(1)$。
## 算法步骤
1. 初始化
- 对于叶子节点 $i$：$f_i(0) = f_i(1) = pos[i]$（在询问序列中的位置）。
2. 后序遍历：
- 从叶子向上计算每个节点的 $f_u(0)$ 和 $f_u(1)$。
- 记录达到最大确定时间时子节点的值选择。
3. 选择最优方案：
- 比较根节点的 $f_{root}(0)$ 和 $f_{root}(1)$。
- 优先判刑 $f_{root}(1)$（如果相等或更大）。
4. 回溯构造解：
- 从根节点开始，根据记录的选择向下分配叶子的值。
AC code
#include <bits/stdc++.h> using namespace std; const int maxnn = 1000005; int n, root; int op[maxnn]; int lc[maxnn], rc[maxnn]; int pos[maxnn]; int mt[maxnn][2]; int cl[maxnn][2], cr[maxnn][2]; vector<int> adj[maxnn]; void bt() {//这个题太BT了pwp root = n + 1; vector<int> parent(2*n, 0); stack<int> st; parent[root] = -1; st.push(root); while (!st.empty()) { int u = st.top(); st.pop(); int cnt = 0; for (int v : adj[u]) { if (v == parent[u]) continue; parent[v] = u; if (cnt == 0) lc[u] = v; else if (cnt == 1) rc[u] = v; cnt++; st.push(v); } } } int main() { scanf("%d", &n); for (int i = 1; i <= n-1; i++) { int v = n + i; scanf("%d", &op[v]); } for (int i = 0; i < 2*n-2; i++) { int u, v; scanf("%d%d", &u, &v); adj[u].push_back(v); adj[v].push_back(u); } bt(); for (int i = 1; i <= n; i++) { int leaf; scanf("%d", &leaf); pos[leaf] = i; } for (int i = 1; i <= n; i++) { mt[i][0] = mt[i][1] = pos[i]; } stack<pair<int,int>> st; st.push({root, 0}); while (!st.empty()) { int u = st.top().first; int state = st.top().second; st.pop(); if (u <= n) continue; if (state == 0) { st.push({u, 1}); if (rc[u]) st.push({rc[u], 0}); if (lc[u]) st.push({lc[u], 0}); } else { int a = lc[u], b = rc[u]; mt[u][0] = mt[u][1] = -1; for (int va = 0; va <= 1; va++) { for (int vb = 0; vb <= 1; vb++) { if (mt[a][va] == -1 || mt[b][vb] == -1) continue; int vu, tu; if (op[u] == 0) { vu = va & vb; if (va == 0 && vb == 0) tu = min(mt[a][va], mt[b][vb]); else if (va == 0 && vb == 1) tu = mt[a][va]; else if (va == 1 && vb == 0) tu = mt[b][vb]; else tu = max(mt[a][va], mt[b][vb]); } else { vu = va | vb; if (va == 1 && vb == 1) tu = min(mt[a][va], mt[b][vb]); else if (va == 1 && vb == 0) tu = mt[a][va]; else if (va == 0 && vb == 1) tu = mt[b][vb]; else tu = max(mt[a][va], mt[b][vb]); } if (tu > mt[u][vu]) { mt[u][vu] = tu; cl[u][vu] = va; cr[u][vu] = vb; } } } } } int rv; if (mt[root][1] >= mt[root][0]) rv = 1; else rv = 0; vector<int> ans(n+1, 0); stack<pair<int,int>> sa; sa.push({root, rv}); while (!sa.empty()) { int u = sa.top().first; int vu = sa.top().second; sa.pop(); if (u <= n) { ans[u] = vu; } else { int va = cl[u][vu]; int vb = cr[u][vu]; sa.push({rc[u], vb}); sa.push({lc[u], va}); } } for (int i = 1; i <= n; i++) { printf("%d", ans[i]); } printf("\n"); return 0; }
