我们记一组询问为 $(s, t)$，不难猜到策略只有两种：

• 要么直接沿树边从 $s$ 走到 $t$。
• 你选一个集合 $S$，然后不断走传送门直到走进 $S$ 中的节点，然后立刻停下沿树边走到 $t$。

前者是随便做的，而 $S$ 确定时后者的期望步数是

$$\frac{n}{|S|} + \frac{\sum_{u \in S} dis(u, t)}{|S|}$$

意义是显然的。首先你每次有 $\frac{|S|}{n}$ 的概率成功跳进集合 $S$，根据经典结论期望次数是 $\frac{n}{|S|}$ 次。其次你会随机出现在这个集合里，那么你走到 $t$ 的期望步数当然就是上式的后一半。

显然当 $|S|$ 固定时，选的节点和 $t$ 距离越近越好。那显然是选前 $|S|$ 大的那些。

到这里就已经有了一个 $O(n^2)$ 的做法，可以获得 $45$ 分。

考场上因为 T1 一直没卡过去，想到这里就没时间了。但其实到这一步已经快要做完了。

进一步地想，可以发现 $S$ 一定是 $t$ 的一个 $k$ - 邻域，也就是所有 $dis(u, t) \le k$ 的节点 $u$ 构成的集合，其中 $k \in [0, n-1]$。

为什么呢？当你加入一个距离为 $D$ 的点时，对答案的贡献是

$$\begin{aligned} \Delta=&\frac{n}{|S+1|} + \frac{D + \sum_{u \in S} dis(u, t)}{|S+1|} - \frac{n}{|S|} - \frac{\sum_{u \in S} dis(u, t)}{|S|} - \\ =& \frac{1}{|S|(|S|+1)} \left(-n +\sum_{u \in S} (D - dis(u, t)) \right) \end{aligned}$$

如果你加入一个距离为 $D$ 的点是优的，则 $\Delta < 0$。这时候再加入另一个距离为 $D$ 的点，除了分母以外没有影响任何东西，因此仍有 $\Delta < 0$。

因此我们就证明了 $S$ 是 $t$ 的一个 $k$ - 邻域。不妨记 $f(t, d)$ 表示选 $t$ 的 $d$ - 邻域时的答案。对于一组询问，我们只需要知道

$$\min_{d = 0}^{n-1} f(t, d)$$

猜一手这个函数是单谷的。事实上根据上面的 $\Delta$ 的正负性可以说明确实如此。

于是我们可以通过二分来回答单组询问，而 $f(t, d)$ 可以通过点分树做到单次 $O(\log n)$ 回答。因此总复杂度是 $O(n \log^2 n + q \log n)$ 的（后面的 $O(q \log n)$ 是在算第一种直接走树边的策略）。

这样可以获得随机分数。

以下给出“谷”的严格定义：第一个满足 $f(t, i) < f(t, i+1)$ 的位置 $i$；如果不存在，我们定义谷是树上所有点与 $t$ 的距离的最大值。

其实不难猜到，原树上相邻节点的“谷”可能是接近的，大概只有 eps 的距离。

可以证明，相邻两个节点的“谷”相差不超过 $1$。

我们考虑所谓“谷”其实就是不断扩大邻域，直到再往里加点的时候，上面的 $\Delta$ 变成了正数时停下。

因为对相邻两个点 $(x, y)$ 而言，所有点到它的 $dis$ 至多变化 $1$，所以 $\Delta$ 中每一个 $(D-dis(u,t))$ 这样的值至多增加或减少 $1$。不妨设 $x$ 的“谷”是 $k$，那么当时考虑的 $D = k+1$。

我们声称 $y$ 的“谷”一定 $\le (k+1)$。因为取 $D=k+2$ 就已经盖过了在树上移动一步让 $\Delta$ 产生的偏移范围，足以让本就是正数的 $\Delta$ 保持正数）。

由于这条性质对任意相邻点都是对称的，我们就可以证明相邻两个点的“谷”相差一定不超过 $1$。

那我们只需要知道一个节点的“谷”，然后在 dfs 的过程中动态维护每个点的“谷”就可以了。实现的时候可能稍微有一点细节。

总时间复杂度 $O((n+q) \log n)$。

#include <bits/stdc++.h>
// #include "teleport.h"
using namespace std;

const int N = 1e6 + 5, M = 4e7 + 5;
vector<int> g[N], G[N];

int mx[N], siz[N], fth[N], dis[N][21], tot, root, tsiz[N], ce[N];
bool vis[N];
vector<int> s1[N], s2[N];
vector<long long> s3[N], s4[N];

void getsiz(int u, int fa)
{
	siz[u] = 1;
	for(auto v : g[u])
	{
		if(v == fa || vis[v]) continue;
		getsiz(v, u);
		siz[u] += siz[v];
	}
	return;
}

void getroot(int u, int fa)
{
	mx[u] = tot - siz[u];
	for(auto v : g[u])
	{
		if(v == fa || vis[v]) continue;
		getroot(v, u);
		mx[u] = max(mx[u], siz[v]);
	}
	if(!root || mx[u] < mx[root]) root = u;
	return;
}

void dfs_dis(int u, int fa, int st, int dep)
{
	dis[u][ce[u] - ce[st]] = dep;
	for(auto v : g[u])
	{
		if(vis[v] || v == fa) continue;
		dfs_dis(v, u, st, dep + 1);
	}
	return;
}

void solve(int u, int c)
{
	ce[u] = c;
	vis[u] = 1, tsiz[u] = 1;
	for(auto v : g[u])
	{
		if(vis[v]) continue;
		getsiz(v, u);
		root = 0, tot = siz[v];
		getroot(v, u);
		
		fth[root] = u;
		int vt = root;
		G[u].push_back(root);
		solve(root, c + 1);
		tsiz[u] += tsiz[vt];
	}
	dfs_dis(u, 0, u, 0);
	vis[u] = 0;
	return;
}

bool operator < (pair<long long, int> x, pair<long long, int> y)
{
	return (x.first * y.second < x.second * y.first);
}

pair<long long, int> min(pair<long long, int> x, pair<long long, int> y)
{
	return (x.first * y.second < x.second * y.first ? x : y);
}

pair<long long, int> max(pair<long long, int> x, pair<long long, int> y)
{
	return (x.first * y.second > x.second * y.first ? x : y);
}

pair<long long, int> calc(pair<long long, int> x)
{
	long long gc = __gcd(x.first, (long long) x.second);
	return {x.first / gc, (int) (x.second / gc)};
}

int dep[N], fs[N][21], n;

void dfs(int u, int fa)
{
	dep[u] = dep[fa] + 1, fs[u][0] = fa;
	for(int i = 1; i <= 20; i++)
		fs[u][i] = fs[fs[u][i - 1]][i - 1];
	for(auto v : g[u])
	{
		if(v == fa) continue;
		dfs(v, u);
	}
	return;
}

inline int LCA(int x, int y)
{
	if(dep[x] < dep[y]) swap(x, y);
	for(int i = 20; i >= 0; i--)
		if(dep[fs[x][i]] >= dep[y]) x = fs[x][i];
	if(x == y) return x;
	for(int i = 20; i >= 0; i--)
		if(fs[x][i] != fs[y][i]) x = fs[x][i], y = fs[y][i];
	return fs[x][0];
}

inline int getdis(int x, int y)
{
	return dep[x] + dep[y] - 2 * dep[LCA(x, y)];
}

pair<long long, int> calcsum(int x, int d) // 查询树上所有距离 x <= d 的点的 dis(i, x) 之和，以及点的数量
{
	pair<long long, int> rp = {n, 0};
	
	for(int r = fth[x], s = x, j = 1; r; r = fth[r], s = fth[s], j++)
	{
		if(d - dis[x][j] < 0) continue;		
		int c1 = s1[r][min(d - dis[x][j], tsiz[r])];
		rp.second += c1;
		rp.first += 1ll * c1 * dis[x][j] + s3[r][min(d - dis[x][j], tsiz[r])];
		
		int c2 = s2[s][min(d - dis[x][j], tsiz[s] + 1)];
		rp.second -= c2;
		rp.first -= 1ll * c2 * dis[x][j] + s4[s][min(d - dis[x][j], tsiz[s] + 1)];
	}
	rp.second += s1[x][min(d, tsiz[x])];
	rp.first += s3[x][min(d, tsiz[x])];
	return rp;
}

pair<long long, int> rs[N];
int pos[N];

void dfs2(int u, int fa)
{
	if(fa)
	{
		rs[u] = calcsum(u, pos[fa]); pos[u] = pos[fa];
		if(pos[fa] - 1 >= 0)
		{
			auto pr = calcsum(u, pos[fa] - 1);
			if(pr < rs[u]) rs[u] = pr, pos[u] = pos[fa] - 1;
		}
		if(pos[fa] + 1 <= n)
		{
			auto pr = calcsum(u, pos[fa] + 1);
			if(pr < rs[u] || pr == rs[u]) rs[u] = pr, pos[u] = pos[fa] + 1;
		}
	}
	else
	{
		int l = 0, r = n - 2;
		rs[u] = calcsum(u, n - 1); pos[u] = n - 1;
		while(r - l > 1)
		{
			int mid = (l + r) >> 1;
			pair<long long, int> p1 = calcsum(u, mid);
			pair<long long, int> p2 = calcsum(u, mid + 1);
			if(p1 < p2 || p1 == p2) pos[u] = mid, rs[u] = p1, r = mid;
			else l = mid;
		}
		
	}
	for(auto v : g[u])
	{
		if(v == fa) continue;
		dfs2(v, u);
	}
	return;
}

vector<pair<long long, int> > teleport(int c, int _n, int m, vector<int> u, vector<int> v, vector<int> x, vector<int> y)
{
	n = _n;
	vector<pair<long long, int> > res;
	for(int i = 0; i < n - 1; i++) 
	{
		u[i]++, v[i]++;
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	getsiz(1, 0);
	root = 0, tot = n;
	getroot(1, 0);
	solve(root, 0);
	
	dfs(1, 0);
	
	tsiz[0] = n;
	int rep = 0;
	
	for(int i = 1; i <= n; i++)
	{
		s1[i].resize(tsiz[i] + 1);
		s2[i].resize(tsiz[i] + 2);
		s3[i].resize(tsiz[i] + 1);
		s4[i].resize(tsiz[i] + 2);
	}	
	
	for(int x = 1; x <= n; x++)
	{
		for(int r = x, j = 0; r; r = fth[r], j++)
		{
			s1[r][dis[x][j]]++;
			s3[r][dis[x][j]] += dis[x][j];
		}
		for(int r = fth[x], s = x, j = 1; r; r = fth[r], s = fth[s], j++)
		{
			s2[s][dis[x][j]]++;
			s4[s][dis[x][j]] += dis[x][j];
		}
	}
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= tsiz[i]; j++)
		{
			s1[i][j] += s1[i][j - 1];
			s3[i][j] += s3[i][j - 1];
		}
		for(int j = 1; j <= tsiz[i] + 1; j++)
		{
			s2[i][j] += s2[i][j - 1];
			s4[i][j] += s4[i][j - 1];
		}
	}
	dfs2(1, 0);
	for(int o = 0; o < m; o++)
	{
		int s = x[o], t = y[o];	s++, t++;
		pair<long long, int> rg = {(long long) getdis(s, t), 1};
		rg = min(rg, rs[t]);
		res.push_back(calc(rg));
	}
	return res;
}