【题解】洛谷P4281 [AHOI2008] 紧急集合（求三个点LCA）

洛谷P4281：https://www.luogu.org/problemnew/show/P4281

思路

答案所在的点必定是三个人所在点之间路径上的一点

本蒟蒻一开始的想法是：先求出2个点之间的LCA 再求出此LCA和第3个点的LCA

但是没有考虑到有可能答案所在点可能比2个点之间的LCA深度更深

因为两点之间的LCA是两点共同能到达的深度最浅的一个点

所以我们可以考虑：

设a=LCA(x,y) 此时x和y到a点为最小花费则此时z到a的花费可以用LCA(a,z)来计算

因此我们分别计算3种情况并取最小值即可

设d为树的深度 a为x和y的LCA b为a与z的LCA 从x到a y到a 分别花费d[x]-d[a]和d[y]-d[a] 从z到a花费d[z]+d[a]-2*d[b]

则ans=max(d[x]+d[y]+d[z]-d[a]-2*d[b])

代码

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

#define maxn 500050

#define INF 1e9+7

int n,m,cnt,ans,a,b,k,x,y,z;

int h[maxn],dep[maxn],f[maxn][];

struct Edge

{

    int next;

    int to;

}e[maxn<<];

void add(int u,int v)

{

    e[++cnt].to=v;

    e[cnt].next=h[u];

    h[u]=cnt;

}

void deal(int u,int fa)//常规预处理

{

    dep[u]=dep[fa]+;

    for(int i=;i<=;i++)

    {

        f[u][i]=f[f[u][i-]][i-];

    }

    for(int i=h[u];i;i=e[i].next)

    {

        int v=e[i].to;

        if(v==fa) continue;

        f[v][]=u;

        deal(v,u);

    }

}

int lca(int x,int y)//常规LCA

{

    if(dep[x]<dep[y]) swap(x,y);

    for(int i=;i>=;i--)

    {

        if(dep[f[x][i]]>=dep[y]) x=f[x][i];

        if(x==y) return x;

    }

    for(int i=;i>=;i--)

    {

        if(f[x][i]!=f[y][i])

        {

            x=f[x][i];

            y=f[y][i];

        }

    }

    return f[x][];

}

void check()

{

    int t=dep[x]+dep[y]+dep[z]-dep[a]-*dep[b];//计算每种情况的ans

    if(t<ans)//如果当前值小于原ans 则替换

    {

        ans=t;

        k=a;//k为最后的位置

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<n;i++)

    {

        scanf("%d%d",&x,&y);

        add(x,y);

        add(y,x);

    }

    deal(,);//预处理

    for(int i=;i<=m;i++)

    {

        ans=INF;//初始化

        scanf("%d%d%d",&x,&y,&z);

        a=lca(x,y);//三种情况分别计算

        b=lca(a,z);

        check();

        a=lca(x,z);

        b=lca(a,y);

        check();

        a=lca(z,y);

        b=lca(a,x);

        check();

        printf("%d %d\n",k,ans);

    }

}

巴特西

【题解】洛谷P4281 [AHOI2008] 紧急集合（求三个点LCA）

思路

代码

最新文章

热门文章