树剖求条 M+T+W 20pts
查看原帖
树剖求条 M+T+W 20pts
697932
yangyafan楼主2025/1/18 09:16
#include <bits/stdc++.h>
using namespace std;
vector<int> v[500010];
int cnt[500010],dep[500010],siz[500010],son[500010],fa[500010],top[500010];
inline void dfs(int x){
	dep[x]=dep[fa[x]]+1,siz[x]=1;
	for(int i=0;i<cnt[x];i++){
		if(v[x][i]==fa[x]) continue;
		fa[v[x][i]]=x,dfs(v[x][i]),siz[x]+=siz[v[x][i]];
		if(!son[x]||son[x]<siz[v[x][i]]) son[i]=v[x][i];
	};
	return ;
}
inline void DFS(int x,int tp){
	top[x]=tp;
	if(son[x]) DFS(son[x],tp);
	for(int i=0;i<cnt[x];i++){
		if(v[x][i]==son[x]||v[x][i]==fa[x]) continue;
		DFS(v[x][i],v[x][i]);
	}
	return ;
}
inline int lca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]]) x=fa[top[x]];
		else y=fa[top[y]];
	}
	if(dep[x]<dep[y]) return x;
	else return y;
}
int main(){
	int n,m;
	cin >>n>>m;
	for(int i=1;i<n;i++){
		int x,y;
		cin >>x>>y;
		cnt[x]++,cnt[y]++,v[x].push_back(y),v[y].push_back(x);
	}
	dfs(1);
	DFS(1,1);
	while(m--){
		int x,y,z,k1,k2,k3,k;
		cin >>x>>y>>z;
		k1=lca(x,y),k2=lca(y,z),k3=lca(x,z);
		if(k1==k2) k=k3;
		else if(k1==k3) k=k2;
		else k=k1;
		cout <<k<<" "<<dep[x]+dep[y]+dep[z]+3*dep[k]-2*(dep[lca(x,k)]+dep[lca(y,k)]+dep[lca(z,k)])<<"\n";
	}
	return 0;
}
2025/1/18 09:16
加载中...