题解：P12393 「RiOI-6」flos

$\text{Upd 2025/5/2}$：修正一些笔误，简化了做法。

## 题意
给定一棵以 $1$ 为根的树。一个人从 $x$ 出发，有 $t$ 秒的时间，往远离根方向每走一个单位就会耗费 $1$ 秒，往靠近根方向走不耗费时间。$q$ 次询问 $x,t$，求能走到的最远的距离。$1\leq n,q\leq 2\times 10^5$，**强制在线**。

## 题解
显然 std 做复杂了。

考虑 $t=n$ 的部分分。这个就是询问从 $x$ 开始走能到达的最远距离，我们有经典的 $\mathcal{O}(n)$ 换根 DP 做法，但这个做法在这题大概是没前途的。

我们给出另一种做法：设这棵树的直径的两端为 $p_1,p_2$，则答案为 $\max(\operatorname{dist}(x,p_1),\operatorname{dist}(x,p_2))$，证明过程和两次 DFS 求直径的正确性证明类似，反证即可，这里不再赘述。

回到原题，加上下行距离不超过 $t$ 的限制，路径有以下几种可能：
- 向下走：答案为 $\min(t,h_x)$，其中 $h_x$ 表示从 $x$ 点向下走能到达的最远距离。
- 向上走：答案为 $dep_x$，其中 $dep_x$ 表示 $x$ 点的深度，$dep_1=0$。
- 走最长链：以 $p_1$ 为例，令 $d=\operatorname{lca}(p_1,x)$，若 $d=p_1$ 或 $d=x$ 我们不作处理，否则答案为 $dep_x-dep_d+\min(t,dep_{p_1}-dep_d)$。$p_2$ 的处理是一样的。

对上面的情况统计答案取最大值即可，时间复杂度 $\mathcal{O}((n+q)\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 = 23;

namespace IO {
	const int S = 1 << 24, lm = 1 << 23;
	char bi[S + 5], bo[S + 5], *p1 = bi, *p2 = bi, *p3 = bo, ch;
	int s, szo;
	inline char gc() {
		if (p1 == p2) p2 = (p1 = bi) + fread(bi, 1, S, stdin);
		return p1 == p2 ? EOF : *p1++;
	}
	inline ll rd() {
		s = 1;
		for (ch = gc(); ch < '0' || ch > '9'; ch = gc()) if (ch == '-') s = -1;
		ll x = 0;
		for (; ch >= '0' && ch <= '9'; ch = gc()) x = x * 10 + (ch ^ 48);
		return s * x;
	}
	inline void pc(char ch) { *p3++ = ch, ++szo; }
	inline void ot() { fwrite(bo, 1, szo, stdout), szo = 0, p3 = bo; }
	inline void fl() { if (szo > lm) ot(); }
	inline void wt(ll x, char sep = '\n') {
		static char tmp[30], *pt; s = 1, pt = tmp;
		if (x < 0) s = -1, x = -x;
		while (*pt++ = (x % 10) ^ 48, x /= 10);
		if (s == -1) *pt++ = '-';
		while (pt-- != tmp) pc(*pt);
		pc(sep), fl();
	}
}
using IO::rd; using IO::wt; using IO::ot;

int n, q, rt, ans, lg2[N];
int h[N], dep[N], hson[N], sz[N], top[N];
int stmp, fa[N], dfn[N], pdfn[N];
int p1, p2, mxp, dis[N];
bool d, ch = 1;

struct AdjList {
	int tot, head[N], nxt[N << 1], to[N << 1];
	inline void init() { tot = 0, memset(head + 1, -1, n << 2); }
	inline void ins(int x, int y) { to[++tot] = y, nxt[tot] = head[x], head[x] = tot; }
} t;

inline void dfs_build(int x) {
	sz[x] = 1;
	for (int i = t.head[x]; ~i; i = t.nxt[i]) {
		int y = t.to[i];
		if (y == fa[x]) continue;
		dep[y] = dep[x] + 1, fa[y] = x, dfs_build(y);
		chk_max(h[x], h[y] + 1), sz[x] += sz[y];
		if (!hson[x] || sz[y] > sz[hson[x]]) hson[x] = y;
	}
}
inline void dfs_decomp(int x, int tp) {
	top[x] = tp, pdfn[dfn[x] = ++stmp] = x;
	if (hson[x]) dfs_decomp(hson[x], tp);
	for (int i = t.head[x]; ~i; i = t.nxt[i]) {
		int y = t.to[i];
		if (y != fa[x] && y != hson[x]) dfs_decomp(y, y);
	}
}
inline void dfs_find(int x, int fx) {
	for (int i = t.head[x]; ~i; i = t.nxt[i]) {
		int y = t.to[i];
		if (y == fx) continue;
		if ((dis[y] = dis[x] + 1) > dis[mxp]) mxp = y;
		dfs_find(y, x);
	}
}
inline int lca(int x, int y) {
	while (top[x] ^ top[y]) dep[top[y]] > dep[top[x]] ? y = fa[top[y]] : x = fa[top[x]];
	return dep[y] > dep[x] ? x : y;
}
inline void upd(int p, int x, int c) {
	int d = lca(p, x);
	if (d == x || d == p) return;
	chk_max(ans, dep[x] - dep[d] + min(c, dep[p] - dep[d]));
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    n = rd(), q = rd(), d = rd(), t.init();
    for (int i = 1, x, y; i < n; ++i) x = rd(), y = rd(), t.ins(x, y), t.ins(y, x);
    for (int i = 2; i <= n; ++i) lg2[i] = lg2[i >> 1] + 1;
    dfs_build(1), dfs_decomp(1, 1);
    dfs_find(mxp = 1, 0), dis[p1 = mxp] = 0, dfs_find(p1, 0), p2 = mxp;
    while (q--) {
    	int x = rd(), c = rd();
    	if (d) x ^= ans, c ^= ans;
    	ans = max(min(c, h[x]), dep[x]);
    	upd(p1, x, c), upd(p2, x, c);
    	wt(ans);
    }
    return ot(), 0;
}
```

正在渲染内容...