题解：P10952 聚会

这道题里，我们可以拿出一棵树：

进行分析，对于

x,y,z

三点，求出他们的

\operatorname{lca}

，并分别记

\operatorname{lca}(x,y),\operatorname{lca}(x,z),\operatorname{lca}(y,z)

为

l1,l2,l3

，可以证明他们之中一定有两个是相等的，而剩下的一个点即为他们所选的目标城市。我们接着通过

\operatorname{lca}

求出三点中两两之间的距离，然后输出我们需要的那个就行了。

下面给出倍增法的代码：

CPP

#include<bits/stdc++.h>
using namespace std;
vector<int>e[500005];
int f[50][500005],dep[500005],n,lim;
void dfs(int u,int fa)
{
    f[0][u]=fa;
	dep[u]=dep[fa]+1;
	for(int i=0;i<e[u].size();i++)
	{
		int v=e[u][i];
		if(v!=fa) dfs(v,u);
	}
}
void init(int sz,int rt)
{
	n=sz;
	lim=__lg(n);
	dep[rt]=1;
	dfs(rt,0);
	for(int i=1;i<=lim;i++)
	{
		for(int u=1;u<=n;u++) f[i][u]=f[i-1][f[i-1][u]];
	} 
} 
int lca(int u,int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=lim;i>=0;i--)
	{
		if(dep[u]-(1<<i)>=dep[v]) u=f[i][u];
	}
	if(u==v) return u;
	for(int i=lim;i>=0;i--)
	{
		if(!f[i][u]) continue;
		if(f[i][u]!=f[i][v])
		{
			u=f[i][u];
			v=f[i][v];
		}
	}
	return f[0][u];
}
//lca的板子 

int dis(int u,int v)
{
	int x=lca(u,v);
	return dep[u]+dep[v]-dep[x]*2;
}
//利用lca求出两点之间的距离 

int main()
{
	int n,q,s;
	cin>>n>>q;
    for(int i=1;i<n;i++)
	{
        int a,b;
		cin>>a>>b;
        e[a].push_back(b);
        e[b].push_back(a);//建边 
    }
    init(n,1);//初始化，求出2的n次方级父亲 
    for(int i=1;i<=q;i++)
	{
		int u,v,w;
		int l1,l2,l3,d1,d2,d3;
		scanf("%d%d%d",&u,&v,&w);
		l1=lca(u,v);
		l2=lca(u,w);
		l3=lca(v,w);//求出lca 
		d1=dis(u,v)+dis(l1,w);
		d2=dis(u,w)+dis(l2,v);
		d3=dis(w,v)+dis(l3,u);//求出距离 
		if(l1==l2)cout<<l3<<" "<<d3<<"\n";
		else if(l1==l3)cout<<l2<<" "<<d2<<"\n";
		else if(l2==l3)cout<<l1<<" "<<d1<<"\n";
	}
	return 0; 
}

当然，这道题可以双倍经验

文章操作

相关推荐

评论

题解：P10952 聚会