题解：P12393 「RiOI-6」flos

## 题意
给定一棵以 $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$ 点向下走能到达的最远距离。
- 向上走：答案为 $\min(t,dep_x-1)$，其中 $dep_x$ 表示 $x$ 点的深度，$dep_1=1$。
- 走最长链：以 $p_1$ 为例，令 $d=\operatorname{lca}(p_1,x)$，若 $d=p_1$ 或 $d=x$ 我们不作处理，否则倍增找到 $d$ 在 $p_1$ 方向的儿子 $s$，答案为 $dep_x-dep_d+\min(t,h_s+1)$。$p_2$ 的处理是一样的。

对上面的情况统计答案取最大值即可，时间复杂度 $\mathcal{O}((n+q)\log{n})$。

## 代码
```cpp
#include <iostream>

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;

int n, q, rt, ans, lg2[N], dep[N], h[N], fa[LGN][N], b[N];
int p1, p2, mxp, dis[N];
bool d, ch = 1;

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

void dfs_pre(int x, int fx) {
	for (int i = 1; i <= lg2[dep[x]]; ++i) fa[i][x] = fa[i - 1][fa[i - 1][x]];
	for (int i = t.head[x]; ~i; i = t.nxt[i]) {
		int y = t.to[i];
		if (y == fx) continue;
		dep[y] = dep[x] + 1, fa[0][y] = x, dfs_pre(y, x);
		chk_max(h[x], h[y] + 1);
	}
}
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;
		dis[y] = dis[x] + 1;
		if (dis[y] > dis[mxp]) mxp = y;
		dfs_find(y, x);
	}
}
int lca(int x, int y) {
	if (dep[x] > dep[y]) swap(x, y);
	for (int i = lg2[dep[y] - dep[x]]; ~i; --i)
		if (dep[fa[i][y]] >= dep[x]) y = fa[i][y];
	if (x == y) return x;
	for (int i = lg2[dep[x]]; ~i; --i)
		if (fa[i][x] ^ fa[i][y]) x = fa[i][x], y = fa[i][y];
	return fa[0][x];
}
int find(int x, int y) {
	for (int i = lg2[dep[y] - dep[x]]; ~i; --i)
		if (dep[fa[i][y]] > dep[x]) y = fa[i][y];
	return y;
}
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, h[find(d, p)] + 1));
}

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