题解：CF2033G Sakurako and Chefir

令 $fa_u$ 为 $u$ 的父亲，$son_u$ 表示 $u$ 的儿子组成的集合。

首先预处理 $f(u)$ 表示 $u$ 的子树内最深的点的深度。

对于一次询问，首先把答案的初始值设为 $f(u)$，表示一步也不向上走。

考虑处理 $g(u)$，表示从 $u$ 走到 $fa_u$ 后，接下来再从别的子树往下走，能走的最多的步数。其实就是我们强制了原题中只能向上走恰好 $1$ 步的答案。

显然：

$$
g(u) = 1 + \max_{v \in son_{fa_u},v \ne u} f(v) - dep(u)
$$

$g(u)$ 也是不难预处理的。

考虑如何计算一次询问 $(u, k)$ 的答案。最暴力的，我们可以枚举向上走几步（$i = 1\dots k$，$i=0$ 即不向上走的已经特判了）。设从 $u$ 开始向上走 $i$ 步后到达的点为 $u_i$。那么答案为：

$$
\max_{i=1}^k i + g(u_{i-1})
$$

考虑**倍增**优化。

具体的，我们设 $w(u, i)$ 表示从 $u$ 开始向上最多走 $2^i$ 步，然后再从别的子树向下走，最多步数。形式化的：

$$
w(u, i) = \max_{j=1}^{2^i} \color{red}j \color{black} + g(u_{j-1})
$$

有递推：

$$
w(u,i) = \max\{w(u,i-1), w(u_{2^{i-1}}, i-1) \color{red}{{}+ 2^{i-1}}\color{black}\}
$$

这里 $+2^{i-1}$ 对应了上面的 $+j$。这是普通倍增所没有的。

查询与预处理类似。于是总复杂度做到 $\mathcal O((n+q)\log n)$。

```cpp
int n;
vector<int> g[N];
int st[N][20], w[N][20];
int mxdep[N], dep[N];

// 定义一条边 (fa[u], u) 的权值为，fa[u] 的所有除 u 的儿子中，mxdep - dep[fa[u]] 的最大值

void dfs1(int u, int fa) {
	mxdep[u] = dep[u] = dep[fa] + 1;
	int k1 = -1e9, k2 = -1e9;
	for (int v : g[u])
		if (v != fa) {
			dfs1(v, u);
			mxdep[u] = max(mxdep[u], mxdep[v]);
			if (mxdep[v] - dep[u] >= k1) {
				k2 = k1, k1 = mxdep[v] - dep[u];
			} else if (mxdep[v] - dep[u] > k2) {
				k2 = mxdep[v] - dep[u];
			}
		}
	
	for (int v : g[u]) {
		if (v == fa) continue;
		w[v][0] = 1 + (mxdep[v] - dep[u] == k1 ? k2 : k1);
	}
}

void dfs2(int u, int fa) {
	for (int v : g[u]) {
		if (v == fa) continue;
		
		st[v][0] = u;
		for (int i = 1; i < 20; ++ i ) {
			st[v][i] = st[st[v][i - 1]][i - 1];
			w[v][i] = max(w[v][i - 1], w[st[v][i - 1]][i - 1] + (1 << i - 1));
		}
		
		dfs2(v, u);
	}
}

void solve() {
	cin >> n;
	
	for (int i = 1; i <= n; ++ i ) {
		g[i].clear();
	}
	
	for (int i = 1; i < n; ++ i ) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	dfs1(1, 0);
	dfs2(1, 0);=
	
	int q;
	cin >> q;
	
	while (q -- ) {
		int u, k;
		cin >> u >> k;
		
		k = min(k, dep[u] - 1);
		int res = max(k, mxdep[u] - dep[u]), lst = 0;
		for (int i = 19; ~i; -- i )
			if (k >= (1 << i)) {
				k -= 1 << i;
				res = max(res, w[u][i] + lst);
				u = st[u][i];
				lst += 1 << i;
			}
		
		cout << res << ' ';
	}
	
	cout << '\n';
}
```

正在渲染内容...