题解：P12393 「RiOI-6」flos
P2441M
·
·
题解
$\text{Upd 2025/5/16}$：走直径的做法假了，改为正确做法。
## 题意
给定一棵以 $1$ 为根的树。一个人从 $x$ 出发，有 $t$ 秒的时间，往远离根方向每走一个单位就会耗费 $1$ 秒，往靠近根方向走不耗费时间。$q$ 次询问 $x,t$，求能走到的最远的距离。$1\leq n,q\leq 2\times 10^5$，**强制在线**。
## 题解
之前走直径的做法假完了，补一发正解。
我们的策略必然是先向上走一段，然后一直向下走。首先考虑一直向上走和一直向下走的情况，此时答案为 $\max(dep_x-1,\min(f_x,t))$，其中 $dep_1=1$，$f_u$ 表示从点 $u$ 向下走能走到的最远距离。
接下来令 $g_u$ 表示从 $fa_u$ 开始不经过 $u$ 能走到的最远距离，则答案就是
$$
\max_{fa_u\in anc(x)}\{dep_x-dep_{fa_u}+\min(t,g_u)\}
$$
拆 $\min$：
- $g_u\geq t$：我们只需取深度最小的 $u$。预处理 $G_u$ 表示 $u$ 到根节点的链上的 $g$ 的最大值，树上倍增跳出深度最小的点 $p$ 即可。
- $g_u<t$：显然 $u$ 必须是 $v$ 的祖先，否则必然不优，于是预处理 $h_u$ 表示 $u$ 到根节点的链上的 $g_v-dep_{fa_v}$ 的最大值即可。
时间复杂度 $\mathcal{O}(n\log{n})$。
## 代码
```cpp
#include <iostream>
#include <cstring>
using namespace std;
#define lowbit(x) ((x) & -(x))
#define chk_min(x, v) (x) = min((x), (v))
#define chk_max(x, v) (x) = max((x), (v))
typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5 + 5, LGN = 18 + 5, INF = 1e9;
int n, q, d, ans, f[N][2], g[N], mxg[N], h[N];
int lg2[N], dep[N], fa[LGN][N];
struct AdjList {
int tot, head[N], nxt[N << 1], to[N << 1];
inline void init(int n) {
tot = 0;
for (int i = 1; i <= n; ++i) head[i] = -1;
}
inline void ins(int x, int y) { to[++tot] = y, nxt[tot] = head[x], head[x] = tot; }
} tree;
inline void init(int n) {
for (int i = 2; i <= n; ++i) lg2[i] = lg2[i >> 1] + 1;
for (int i = 1; i <= n; ++i) h[i] = -INF;
tree.init(n);
}
inline void dfs1(int x) {
for (int i = 1; i <= lg2[dep[x]]; ++i) fa[i][x] = fa[i - 1][fa[i - 1][x]];
for (int i = tree.head[x]; ~i; i = tree.nxt[i]) {
int y = tree.to[i];
if (y == fa[0][x]) continue;
fa[0][y] = x, dep[y] = dep[x] + 1, dfs1(y);
if (f[y][0] + 1 > f[x][0]) f[x][1] = f[x][0], f[x][0] = f[y][0] + 1;
else chk_max(f[x][1], f[y][0] + 1);
}
}
inline void dfs2(int x) {
for (int i = tree.head[x]; ~i; i = tree.nxt[i]) {
int y = tree.to[i];
if (y == fa[0][x]) continue;
g[y] = f[x][(f[y][0] + 1) == f[x][0]], mxg[y] = max(mxg[x], g[y]);
h[y] = max(h[x], g[y] - dep[x]);
dfs2(y);
}
}
inline int query(int x, int t) {
for (int i = lg2[dep[x]]; i >= 0; --i)
if (mxg[fa[i][x]] >= t) x = fa[i][x];
return fa[0][x];
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> q >> d, init(n);
for (int i = 1, u, v; i < n; ++i) cin >> u >> v, tree.ins(u, v), tree.ins(v, u);
dep[1] = 1, dfs1(1), dfs2(1);
while (q--) {
int x, t; cin >> x >> t;
if (d) x ^= ans, t ^= ans;
if (x == 1) ans = min(t, f[x][0]);
else if (!t) ans = dep[x] - 1;
else if (mxg[x] < t) ans = max(min(t, f[x][0]), dep[x] + h[x]);
else {
int y = query(x, t);
ans = max(min(t, f[x][0]), dep[x] - 1);
if (y) chk_max(ans, dep[x] + max(h[y], t - dep[y]));
}
cout << ans << '\n';
}
return 0;
}
```