题解 P4281 【[AHOI2008]紧急集合 / 聚会】

· · 题解

关于这道题倍增求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;
}

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