题解：P10952 聚会

zhangxiaohan007 · 2024-12-07 10:48:21 · 题解

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

进行分析，对于 x,y,z 三点，求出他们的 \operatorname{lca}，并分别记 \operatorname{lca}(x,y),\operatorname{lca}(x,z),\operatorname{lca}(y,z) 为 l1,l2,l3，可以证明他们之中一定有两个是相等的，而剩下的一个点即为他们所选的目标城市。我们接着通过 \operatorname{lca} 求出三点中两两之间的距离，然后输出我们需要的那个就行了。

下面给出倍增法的代码：

#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; 
}

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