自动搬运

查看原文

来自洛谷，原作者为

	高天昊 这个家伙很懒，但也好歹留下了点什么

搬运于2025-08-24 21:58:29，当前版本为作者最后更新于2018-10-10 13:13:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

关于这道题倍增求LCA的做法

看到大佬们都用树链剖分做，可我太菜了不会树链剖分......

不过这道题如果用RMQ做的话只有80分 好像是因为我不会卡常

所以步入正题

关于这道题为什么求LCA其他题解已经解释得很明确了，所以我只是概述一下。

题目要求得出三个点走到同一个点所要求的最小花费，经过我们的分析可以得出这个公共的点较其他点优的情况可以通过 求三个点两两之间的LCA得出，然后我们发现这三个LCA中有二者重合即它存在两种情况:最后三者所走到的最优公共点只可能为这二者之一。

然后经过分析可以得到不重合的公共点才是最优解，大家可以拿笔模拟一下或者感性理解（不重合的公共点情况下 一个单独的点移动比另两个点移动距离要多，较另外一种情况花费当然更低）。

既然是几个人走到一起最小花费，显然是求LCA的同时维护一下深度，~~当然这是倍增所必需的

然后运用差分的思想（假设两点 一点深度为d1,另一点深度为d2,它们LCA深度为d3,这二者之间的距离即为d1+d1-2*d3,只要将这两点推广成三点即可）计算一下最小花费(这个第一篇题解已经非常详细，不会的同学可以去看一看)

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
long long ans=0;
int fa[500010][25],lg[500010],deep[500010],t;
struct node
{
	int from;
	int to;
	int next;
}ed[2*500001];
int v[2*500001],tot=0;
void add(int x,int y)
{
	ed[++tot].from=x;
	ed[tot].to=y;
	ed[tot].next=v[x];
	v[x]=tot;
}
int lca(int x,int y)
{
	if(deep[x]<deep[y])			//假设x深度大于y
		swap(x,y);
	while(deep[x]>deep[y])		//x,y调整到同一深度	
	{
		x=fa[x][lg[deep[x]-deep[y]]-1];
	}
	if(x==y)
		return x;
	for(int k=lg[deep[x]];k>=0;k--)		//x,y一起向上跳
	{
	    if(fa[x][k]!=fa[y][k])
	    {
	    	x=fa[x][k];
			y=fa[y][k];
	    }
	}
    return fa[x][0];
	
}
void dfs(int x,int fath)				
{
	deep[x]=deep[fath]+1;					//处理深度
	fa[x][0]=fath;
	for(int i=1;(1<<i)<=deep[x];i++)
	{
		fa[x][i]=fa[fa[x][i-1]][i-1];
	}
	for(int i=v[x];i;i=ed[i].next)
		if(ed[i].to!=fath)
			dfs(ed[i].to,x);
}
int n,m;
int a,b,c;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n-1;i++)
	{
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)								//常数优化 
		lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	for(int i=1;i<=m;i++)
	{
		ans=0;
		scanf("%d%d%d",&a,&b,&c);
		int t1=lca(a,b);					//三者分别求LCA
		int t2=lca(a,c);
		int t3=lca(b,c);
		if(t1==t2)
			t=t3;
		else if(t1==t3)
			t=t2;
		else if(t2==t3)
			t=t1;
        //差分
		ans=deep[a]+deep[b]+deep[c]-deep[t1]-deep[t2]-deep[t3];		
		printf("%d %lld\n",t,ans);
	}
	return 0;
} 

这份题解可能会有瑕疵，敬请各位大佬斧正。