专栏文章

题解:P10952 聚会

P10952题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir3anq7
此快照首次捕获于
2025/12/04 15:03
3 个月前
此快照最后确认于
2025/12/04 15:03
3 个月前
查看原文

P10952 聚会

思路

考虑倍增 LCA 算法。
每次询问分别求三个点中每两个点的 LCA 点,然后分别求出这三个点到此 LCA 点的距离和,并取最小值即可。
值得一提的是,某两点间的距离不一定是两者的 depthdepth 之差,而需求出两者的 LCA 点,再分别求两者与 LCA 点的 depthdepth 之差,其之和才为距离。

code

CPP
#include<bits/stdc++.h>
#include<queue>
using namespace std;
const int N=500010,M=1000010,INF=0x3f3f3f3f;
int n,m;
int h[N],e[M],ne[M],idx;
int depth[N],fa[N][25];
queue<int> q;
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void bfs()
{
	memset(depth,0x3f,sizeof depth);
	depth[0]=0,depth[1]=1;
	q.push(1);
	while(q.size())
	{
		int t=q.front();
		q.pop();
		for(int i=h[t];~i;i=ne[i])
		{
			int j=e[i];
			if(depth[j]>depth[t]+1)
			{
				depth[j]=depth[t]+1;
				q.push(j);
				fa[j][0]=t;
				for(int k=1;k<=18;k++)
				{
					fa[j][k]=fa[fa[j][k-1]][k-1];
				}
			}
		}
	}
}
int lca(int a,int b)
{
	if(depth[a]<depth[b]) swap(a,b);
	for(int i=18;i>=0;i--)
	{
		if(depth[fa[a][i]]>=depth[b]) a=fa[a][i];
	}
	if(a==b) return b;
	for(int i=18;i>=0;i--)
	{
		if(fa[a][i]!=fa[b][i])
		{
			a=fa[a][i];
			b=fa[b][i];
		}
	}
	return fa[a][0];
}
int dist(int a,int b)
{
	int t=lca(a,b);
	return abs(depth[t]-depth[a])+abs(depth[t]-depth[b]);
}
int check(int x,int y,int z,int ver)
{
	return dist(x,ver)+dist(y,ver)+dist(z,ver);
}
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0)->sync_with_stdio(0);
	cin>>n>>m;
	memset(h,-1,sizeof h);
	for(int i=1;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		add(a,b),add(b,a);
	}
	bfs();
	while(m--)
	{
		int x,y,z;
		cin>>x>>y>>z;
		int res=0,minn=INF;
		int a=lca(x,y),b=lca(x,z),c=lca(y,z);
		if(minn>check(x,y,z,a)) res=a,minn=check(x,y,z,a);
		if(minn>check(x,y,z,b)) res=b,minn=check(x,y,z,b);
		if(minn>check(x,y,z,c)) res=c,minn=check(x,y,z,c);
		cout<<res<<" "<<minn<<'\n';
	}
	return 0;
}

评论

0 条评论,欢迎与作者交流。

正在加载评论...