G. Sakurako and Chefir

来源：Codeforces Round 981 (Div. 3)

链接：Problem - G - Codeforces

思路：

1. 题意是向上走会损失体力，向下走不会损失体力，赛时看反了，搞了好久自己编的问题。
2. 引理1：在一棵树上，距离一个点最远的点是树的两个直径端点
3. 引理2：小的子树的直径一定小于大的子树
4. 引理3：包含一个子树$U$的更大树的直径端点一定距离这个子树$U$内的点更远
5. 由引理3，我们可以推导出来，我们要尽可能地向上走到距离该点最远的祖先$v$。
6. 由引理1，我们可以推导出$v$的子树的直径的一个端点就是距离所求点的最远点。
7. 所以我们首先考虑如何到达距离该点最远的祖先$v$，这里我们可以先求出整棵树的$LCA$，然后使用类似求$lca$的二进制拆分的跳点方式向上跳$k$个点。

		int v, k;int ret = k;
		cin >> v >> k;
		int now = v;
		int tip = 0;
		if (k >= dep[v]) {
			now = 1;
		}
		else {//倍增向上跳点到距离x为k的祖先上
			while (k) {
				if (k & 1) {
					now = lca.fa[now][tip];
				}
				k >>= 1;
				tip++;
			}
		}	

8. 而下一步我们就要求出所有点的子树的直径。
9. 引理4：设两棵树的直径端点点对分别为{$u_1,u_2$}，{$u_3,u_4$}合并两颗树的时候，所形成的新的直径端点$n{v}_1,n{v}_2\in${$u_1,u_2,u_3,u_4$}，也就是说，新的直径的两个端点，一定是之前两棵树直径的四个端点之二。
10. 所以由引理4，我们就可以愉快地将一个点的两棵子树合并起来，并且求出直径了。

#include<bits/stdc++.h>
using namespace std;
#define ll  long long 

struct lca_st {

	vector<int>dep;
	vector<vector<int>>fa;

	void init(int n) {
		fa = vector<vector<int>>(n + 1, vector<int>(30));
		dep = vector<int>(n + 1);
		dep[0] = -1;
	}

	void dfs(int u, int father, vector<vector<int>>& e) {
		dep[u] = dep[father] + 1;
		fa[u][0] = father;
		for (int i = 1; i <= 20; i++)
			fa[u][i] = fa[fa[u][i - 1]][i - 1];

		for (auto v : e[u])
			if (v != father)
				dfs(v, u, e);
	}

	int lca(int u, int v) {
		if (dep[u] < dep[v])
			swap(u, v);
		for (int i = 20; i >= 0; i--)
			if (dep[fa[u][i]] >= dep[v])
				u = fa[u][i];
		if (u == v)
			return v;
		for (int i = 20; i >= 0; i--)
			if (fa[u][i] != fa[v][i])
				u = fa[u][i], v = fa[v][i];
		return fa[u][0];
	}
};
vector<int>dep;
vector<vector<int>> e;
vector<int>nd1, nd2;//记录直径的两个端点
vector<int>len;//存点x的子树的直径长度
lca_st lca;
int get(int a, int b) {//求两点距离
	return lca.dep[a] + lca.dep[b] - 2 * lca.dep[lca.lca(a, b)];
}
void dfs(int x, int fa) {
	nd1[x] = nd2[x] = x;
	dep[x] = dep[fa] + 1;

	//动态维护x子树的直径
	//每次做两棵树的直径合并操作
	for (auto a : e[x]) {
		if (a == fa)	continue;
		dfs(a, x);
		vector<int>ends = { nd1[x],nd2[x],nd1[a],nd2[a] };
		for (int i = 0; i < 4; i++) {
			for (int j = i + 1; j < 4; j++) {
				int dist = get(ends[i], ends[j]);
				if (dist > len[x]) {
					len[x] = dist;
					nd1[x] = ends[i];
					nd2[x] = ends[j];
				}
			}
		}
	}
}
void solve() {

	int n; cin >> n;
	len = nd1 = nd2 = dep = vector<int>(n + 1);
	e = vector<vector<int>>(n + 1);

	for (int i = 1; i < n; i++) {
		int a, b; cin >> a >> b;
		e[a].push_back(b);
		e[b].push_back(a);
	}

	lca.init(n);
	lca.dfs(1, 0, e);
	dep[0] = -1;
	dfs(1, 0);

	int q; cin >> q;
	vector<int>rs;
	while (q--) {
		int v, k;
		cin >> v >> k;
		int ret = k;
		int now = v;
		int tip = 0;
		if (k >= dep[v]) {
			now = 1;
		}
		else {
			while (k) {
				if (k & 1) {
					now = lca.fa[now][tip];
				}
				k >>= 1;
				tip++;
			}
		}

		int len1 = get(nd1[now], v);
		int len2 = get(nd2[now], v);
		rs.push_back(max({ len1, len2 ,min(dep[v],ret) }));
	}
	for (auto a : rs)
		cout << a << ' ';

	cout << endl;

}
signed main() {

	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll T;
	T = 1;

	cin >> T;
	while (T--)
		solve();

	return 0;
}