题解：P4116 Qtree3
CYFqwq
·
·
题解
闲话
:::info[闲话]
在写完 LCA 模板题的 题解 之后，我本以为这个 trick 只能用于求 LCA 了。后来继续研究时，我发现这个 trick 的性质非常有意思，于是我就思考能否用它来解决其它树上问题。
我首先想到的是树链剖分模板题，然而链加链求和被转化为矩形加矩形求和后，需要使用树套树或 KD-Tree 维护，这两种做法要么常数大，要么巨难写，都会被树剖薄纱，所以毫无意义。
然后我就做到了这道题，这个 trick 所有良好的性质简直就是为这个题量身定制的，于是我瞬间有了思路，开始实现代码。
第一遍 AC，轻松获得最优解（697 \text{ ms}），然而我并不满足，于是接着卡常。
经过一系列卡常后，成功获得新的 最优解，领先过去的最优解整整 335 \text{ ms}，这么 nb 的事情，怎么能不庆祝一下呢？
因此我发了一个 帖子，却无人问津（本身这个帖子也比较无意义）。
题意
给出一棵 n 个点的树，以 1 为根，节点有一个颜色，初始时全为白。
有两种操作：
- 翻转点 x 的颜色（白变黑，黑变白）。
- 查询点 v 的所有祖先中，深度最小的黑点，若无，输出 -1。
题解
我们维护两个序列 \mathrm{dfn},\mathrm{rdfn}，\mathrm{dfn}_i 表示节点 i 在 DFS 序列中的位置，\mathrm{rdfn}_i 表示翻转所有节点的儿子列表后，得到的新 dfn。
我们不难发现，节点 u 是节点 v 的祖先，当且仅当 \mathrm{dfn}_u\le\mathrm{dfn}_v\land\mathrm{rdfn}_u\le\mathrm{rdfn}_v。
:::info[简单的证明]
当 u 在 v 的子树内且 u\not=v 时，条件显然不会成立，因此下面只考虑 u,v 没有祖先关系的情况。
我们不妨令 \mathrm{dfn}_u<\mathrm{dfn}_v。
设 l=\mathrm{lca}(u,v)，则 u 和 v 一定分别位于 l 的两个不同儿子的子树内（否则 l 就不是 u,v 的最近公共祖先）。
| 那么在第一遍 DFS 时，会先遍历 u，再遍历 v，第二遍 DFS 就会先遍历 v，再遍历 u，因此 \mathrm{dfn}_u\le \mathrm{dfn}_v\land\mathrm{rdfn}_u\le \mathrm{rdfn}_v 不会成立。 |
我们令 a_{\mathrm{dfn}_u}=\mathrm{rdfn}_u，不难发现 a 也是一个排列（不过这没什么用）。
我们维护一棵线段树，叶子节点 $[u, u]$ 的权值 $v$ 表示：
+ 若 $u$ 是白点，$v=\infty$。
+ 若 $u$ 是黑点，$v=a_u$。
每个非叶子节点维护区间内叶子节点的权值最小值。
对于一次询问，我们线段树二分，找到一个下标最小的、值 $\le \mathrm{rdfn}_v$ 的位置。如果找不到，或者这个位置 $>\mathrm{dfn}_v$，则无解；否则，我们就用这个位置对应的原树上的节点当作答案（因为 $a$ 序列的下标是 $\mathrm{dfn}$，所以我们还要维护 $\mathrm{rk}_i$ 表示 $\mathrm{dfn}_x=i$ 的 $x$）。
然后我们就做完了这个题！
以下是一份没有经过卡常的 AC 代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int cnt1, cnt2;
const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int dfn[N], rdfn[N], tr[N*4], rk[N], col[N];
vector<int> g[N];
void dfs1(int u, int fa) {
dfn[u] = ++cnt1;
rk[cnt1] = u;
for (auto v : g[u]) {
if (v == fa) continue;
dfs1(v, u);
}
// 解决第一次 dfs 后顺便翻转儿子列表
reverse(g[u].begin(), g[u].end());
}
void dfs2(int u, int fa) {
rdfn[u] = ++cnt2;
for (auto v : g[u]) {
if (v == fa) continue;
dfs2(v, u);
}
}
void pushup(int p) {
tr[p] = min(tr[p<<1], tr[p<<1|1]);
}
void update(int p, int l, int r, int x, int k) {
if (l == r) {
tr[p] = k;
return ;
}
int mid = (l + r) >> 1;
if (x <= mid) {
update(p<<1, l, mid, x, k);
} else {
update(p<<1|1, mid+1, r, x, k);
}
pushup(p);
}
int query(int p, int l, int r, int x) {
if (l == r) {
return l;
}
if (tr[p] > x) {
// 最小值 > x，说明区间内不存在 <= x 的值，直接返回 0 表示答案不存在
return 0;
}
int mid = (l + r) >> 1;
if (tr[p<<1] <= x) {
// 左子树存在答案，递归到左子树
return query(p<<1, l, mid, x);
} else {
// 左子树不存在，递归到右子树
return query(p<<1|1, mid+1, r, x);
}
}
int main() {
// 初始时节点都是白色，设置极大值
memset(tr, 0x3f, sizeof(tr));
int n, q;
cin >> n >> q;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(1, 0);
dfs2(1, 0);
while (q--) {
int op, x;
cin >> op >> x;
if (op == 0) {
col[x] ^= 1;
if (col[x] == 1) {
// 黑色，设为 rdfn
update(1, 1, n, dfn[x], rdfn[x]);
} else {
// 白色，设为 inf
update(1, 1, n, dfn[x], inf);
}
} else {
int ans = query(1, 1, n, rdfn[x]);
if (ans == 0 || ans > dfn[x]) {
cout << "-1" << endl;
} else {
cout << rk[ans] << endl;
}
}
}
return 0;
}
```
### 卡常小技巧
只是通过题目怎么能满足贪婪的我呢？我要抢最优解！
#### 技巧 $1$：$\mathrm{rdfn}$ 优化
设 $\mathrm{out}_u$ 为 $u$ 退出 DFS 的时间戳，则 $\mathrm{rdfn_u}=n-\mathrm{out_u}+1$。这个性质可以自己手玩或归纳证明一下。
因此我们可以通过一次 DFS 同时求出 $\mathrm{dfn}$ 和 $\mathrm{rdfn}$：
```cpp
// cnt1 的初始值是 0
// cnt2 的初始值是 n
void dfs(int u, int fa) {
dfn[u] = ++cnt1;
rk[dfn[u]] = u;
for (auto v : g[u]) {
if (v == fa) continue;
dfs(v, u);
}
// 退出 DFS 的时间戳的逆序，因此是 cnt2--
rdfn[u] = cnt2--;
}
```
#### 技巧 $2$：DFS 递归变迭代
这个没什么好说的，不放代码。
#### 技巧 $3$：线段树递归变迭代
这个也没什么好说的，放代码。
```cpp
inline void update(int x) {
int p = x+m-1; // 此处使用堆式线段树，m 表示 >= n 的最小 2 的整数次幂
tr[p] = b[x] ? a[x] : inf; // b 表示节点 x 的颜色，a 即上文的 a 序列
while (p > 1) p >>= 1, tr[p] = min(tr[p<<1], tr[p<<1|1]); // 更新链
}
inline int query(int x) {
if (tr[1] > x) return inf; // 先特判
int p = 1, l = 1, r = m, mid;
while (l < r) mid = (l + r) >> 1, tr[p<<1] <= x ? (r = mid, p <<= 1) : (l = mid+1, p = p<<1|1); // 线段树二分
return l;
}
```
~~压行有亿点严重，凑合看吧。~~
#### 技巧 $4$：链式前向星优化
由于我们不需要真的翻转存儿子的链表，所以我们可以使用链式前向星存图。
~~相信能做这题的人应该都会链式前向星吧。~~
#### 技巧 $5$：快读快写
~~这个我是真不想说了。~~
---
至此，我们就做完了这道题。
该做法截至 $2026$ 年 $7$ 月 $28$ 日 $23:20$ 是本题的最优解，比次优解快 $335 \text { ms}$。
看了这么久了，点个赞吧！