ABC298Ex

水紫。

多次询问 \(L,R\)，求出 \(\sum\limits_{i=1}^n \min(d(i,L),d(i,R))\)。

不失一般性的令 \(del_L\le del_R\)。

分几部分考虑。

• \(L\) 或 \(R\) 的子树中。

预处理 \(f_i\) 代表 \(i\) 的子树中的点到 \(i\) 的距离和，\(s_i\) 代表 \(i\) 的子树大小。

转移方程：\(f_i=\sum\limits_{j\in son_i}f_j+s_j\)，\(s_i=1+\sum\limits_{j\in son_i}s_j\)。

该部分的答案为 \(f_L+f_R\)。

• 不在 \(L\) 和 \(R\) 的 \(\operatorname{lca}\) 的子树中。

令 \(k\) 为 \(\operatorname{lca}(L,R)\)。

该部分的路径一定是形如 \(i\rightarrow k\rightarrow L/R\)。后半部分取决于 \(d(k,L)\) 和 \(d(k,R)\) 谁更小，令 \(m=\min(d(k,L),d(k,R))\)。

前半部分是简单的换根 dp，令 \(g_i\) 代表不在 \(i\) 的子树中的点到 \(i\) 的距离和。

转移方程：\(g_i=g_{fa}+(n-s_{fa})+f_{fa}-(f_p+s_p)+s_{fa}-s_p=g_{fa}+f_{fa}+n-f_p-2\times s_p\)。

该部分答案为 \(g_k+(n-s_k)\times m\)。

• 在 \(L\rightarrow R\) 路径上的点的子树中。

#include <bits/stdc++.h>
#define int long long
//using namespace std;
#define debug(...) fprintf(stderr,##__VA_ARGS__)
void file(){
	freopen("x.in","r",stdin);
	freopen("x.out","w",stdout);
}
const int maxn=2e5+10;

std::vector<int>a[maxn];

int s[maxn],g[maxn],f[maxn],n,m,dis[maxn];

namespace LCA{
	int cnt=0,tot=0,dfn[maxn*4],st[maxn][30],lg[maxn*2],fir[maxn],ys[maxn],fdfn[maxn];
	void dfs(int p,int fa){
//		dfn[++cnt]=p;
		fir[p]=++tot;
		ys[tot]=p;
		dfn[++cnt]=fir[p];
		fdfn[p]=cnt;
		for(int i:a[p]){
			if(i==fa) continue;
			dfs(i,p);
			dfn[++cnt]=fir[p];
		}
	}
	void init(){
		cnt=tot=0;
		dfs(1,0);
		lg[0]=-1;
		for(int i=1;i<=cnt;i++) lg[i]=lg[i>>1]+1;
		for(int i=1;i<=cnt;i++) st[i][0]=dfn[i];
		for(int j=1;j<=20;j++)
			for(int i=1;i+(1ll<<j)-1<=cnt;i++) st[i][j]=std::min(st[i][j-1],st[i+(1ll<<(j-1))][j-1]);
	}
	int qST(int l,int r){
		if(l>r) std::swap(l,r);
		int len=r-l+1;
		debug("lglen=%lld\n",lg[len]);
		return std::min(st[l][lg[len]],st[r-(1ll<<lg[len])+1][lg[len]]);
	}
	int lca(int u,int v){
		return ys[qST(fdfn[u],fdfn[v])];
	}
}

void dfs1(int p,int fa){
	dis[p]=dis[fa]+1;
	s[p]=1;
	f[p]=0;
	for(int i:a[p]){
		if(i==fa) continue;
		dfs1(i,p);
		s[p]+=s[i];
		f[p]+=s[i]+f[i];
	}
	debug("p=%lld f=%lld s=%lld\n",p,f[p],s[p]);
	return ;
}

void dfs2(int p,int fa){
	if(p==1) g[1]=0;
	else g[p]=g[fa]+n-s[fa]+f[fa]-f[p]-s[p]+s[fa]-s[p];
	for(int i:a[p]){
		if(i==fa) continue;
		dfs2(i,p);
	}
	debug("p=%lld g=%lld\n",p,g[p]);
	return ;
}

void check_dfn(){
	debug("checking dfn:\n");
	for(int i=1;i<=LCA::cnt;i++) debug("i=%lld dfn=%lld\n",i,LCA::dfn[i]);
	debug("bh:\n");
	for(int i=1;i<=n;i++) debug("i=%lld fir=%lld f=%lld\n",i,LCA::fir[i],LCA::fdfn[i]);
}

signed main(){
	std::cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		std::cin>>u>>v;
		a[u].push_back(v),a[v].push_back(u);
	}
	dfs1(1,0);
	dfs2(1,0);
	LCA::init();
	check_dfn();
	std::cin>>m;
	while(m--){
		int u,v;
		std::cin>>u>>v;
		debug("lca=%lld\n",LCA::lca(u,v));
		if(LCA::lca(u,v)==u||LCA::lca(u,v)==v){
			if(LCA::lca(u,v)==v) std::swap(u,v);
			std::cout<<f[v]+f[u]-f[v]-s[v]*(dis[v]-dis[u])+g[u]-f[u]<<"\n";
			continue;
		}
		std::cout<<f[u]+f[v]+g[LCA::lca(u,v)]-f[LCA::lca(u,v)]+(n-s[u]-s[v])*(std::min(dis[u],dis[v])-dis[LCA::lca(u,v)])<<"\n";
	}
}
/*
North London forever
*/