$MnZn$ 使用的是倍增 $LCA$ 维护路径。

求出 $(x,LCA(x,y))$ 与 $(y,LCA(x,y))$ 再加上 $x,y,LCA(x,y)$ 的点权

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
const int M=1e5+7;
struct edge{
	int nxt,v;
}e[M<<1];
int h[N],cnt;
void add_edge(int u,int v){
	e[++cnt].nxt=h[u],e[cnt].v=v;
	h[u]=cnt;
}
int n,m;
int d[N],w[N];
int fa[N][20],dis[N][20];
void dfs(int u,int father){
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==father) continue;
		d[v]=d[u]+1;
		fa[v][0]=u;
		dis[v][0]=w[u];
		dfs(v,u);
	}
}
void init(){
	for(int i=1;i<=18;i++)
		for(int j=1;j<=n;j++)
			fa[j][i]=fa[fa[j][i-1]][i-1],dis[j][i]=dis[fa[j][i-1]][i-1]+dis[j][i-1];
}
int LCA(int x,int y){
	if(d[x]<d[y]) swap(x,y);
	int sum=w[x];
	if(x==y) return sum;
	for(int i=18;i>=0;i--)
		if(d[fa[x][i]]>=d[y])
			sum+=dis[x][i],x=fa[x][i];
	if(x==y) return sum;
	for(int i=18;i>=0;i--)
		if(fa[x][i]!=fa[y][i])
			sum+=dis[x][i]+dis[y][i],x=fa[x][i],y=fa[y][i];
	return sum+w[y]+w[fa[x][0]];
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add_edge(u,v),add_edge(v,u);
		w[u]++,w[v]++;
	}
	d[1]=1;
	dfs(1,0);
	init();
	while(m--){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n",LCA(x,y));
	}
	return 0;
}