机房 LCA 和 前缀和

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define N 100005
ll n,m; 
vector<ll> e[N];
ll fa[N],sz[N],son[N],top[N],dep[N];
ll s[N],a[N]; 
void dfs1(ll u,ll f){
	fa[u]=f,dep[u]=dep[f]+1,sz[u]=1;
	for(int v:e[u]){
		if(v==f)continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[son[u]]<sz[v])son[u]=v;
	}
}
void dfs2(ll u,ll t){
	top[u]=t;
	if(!son[u])return;
	dfs2(son[u],t);
	for(int v:e[u]){
		if(v==fa[u]||v==son[u])continue;
		dfs2(v,v);
	}
}
int lca(ll u,ll v){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		u=fa[top[u]];
	}
	return dep[u]<dep[v]?u:v;
}
void dfs(ll u){
	for(int v:e[u]){
		if(v==fa[u])continue;
		s[v]+=s[u];
		dfs(v);
	} 
} 
int main(){
	cin>>n>>m;
	for(ll i=1;i<n;i++){
		ll u,v;scanf("%lld%lld",&u,&v);
		e[u].push_back(v); 
		e[v].push_back(u);
	}
	dfs1(1,0),dfs2(1,1);
	for(ll i=1;i<=n;i++){
		s[i]=e[i].size();
		a[i]=e[i].size();
	}
	dfs(1);
	//for(ll i=1;i<=n;i++)cout<<s[i]<<endl;
	for(ll i=1;i<=m;i++){
		ll u,v;
		scanf("%lld%lld",&u,&v);
		ll kkk=s[u]+s[v]-2*s[lca(u,v)]+a[lca(u,v)];
		printf("%lld\n",kkk);
	} 
	return 0;
}