[Ahoi2008]Meet 紧急集合

2022-07-11 21:38:21

1787: [Ahoi2008]Meet 紧急集合

Time Limit: 20 Sec Memory Limit: 162 MB
http://www.lydsy.com/JudgeOnline/problem.php?id=1787

Description

Input

Output

Sample Input

6 4
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6

Sample Output

5 2
2 5
4 1
6 0

HINT

Source

Day1

结论1：集合点一定在某两个点的lca上

结论2: 3个点两两算出lca，至少有2个lca相同

结论3：不同的那个lca（或3个都相同的lca）就是集合点，3个点到这个点的总距离最小

证明1：如图所示，假设等待点是 3、5、10

3个点之间的路径用蓝色标注，其余路径用橙色标注

要证明结论1，可以证明以下几点：

① 集合点选在蓝色路径上的点一定比选在橙色路径上的点更优

证明：如果集合点选在橙色路径上，即三个点可以不经过集合点到达其他点，那么选橙色路径顶端的蓝色路径上一点会更优

例如上图中 8号点要比13号点更优

② 集合点若选的不是lca，那么集合点越靠近lca，越优。

我们假设选的点

证明：设点a，b，c，lca为a和b的lca，设选的点d不是lca，d往lca方向移动一点，设这一点为e

那么由d向e的过程，会使①2个点的路径长度-1,另外1个点的路径长度+1 或者② 3个点的路径长度各-1

例子：①在上图中选3、5、10，集合点由4向2转移 ②在上图中好像没有。。。画一个三叉树，集合点由上往下移即可

综上可证结论1

有了结论1，就可以做这个题了，3个lca挨着算一遍即可

结论2关键点：点向上的路径有且只有唯一的一条

结论3关键点：相同的那个lca一定在另一个lca的上面

这样就可以只算那一个lca即可

然后，剩下的难以描述（语文不好），画图意会吧...

代码一：算3个lca && 倍增求lca && 读入优化结果：上图第3行

#include<algorithm>

#include<cstdio>

#include<cmath>

#define N 500001

using namespace std;

int n,m,id[N],cnt,fa[N][],p,deep[N],tmp;

int front[N],next[N*],to[N*],tot;

int lca1,lca2,lca3;

int read()

{

    int x=; char c=getchar();

    while(c<''||c>'') c=getchar();

    while(c>=''&&c<='') { x=x*+c-''; c=getchar();}

    return x;

}

void add(int x,int y)

{

    to[++tot]=y; next[tot]=front[x]; front[x]=tot;

    to[++tot]=x; next[tot]=front[y]; front[y]=tot;

}

void dfs(int x)

{

    id[x]=++cnt;

    for(int i=front[x];i;i=next[i])

     if(to[i]!=fa[x][])

     {

          fa[to[i]][]=x;

          deep[to[i]]=deep[x]+;

          dfs(to[i]);

     }

}

int lca(int x,int y)

{

    if(x==y) return x;

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

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

     if(id[fa[x][i]]>id[y])

      x=fa[x][i];

    return fa[x][];

}

int dis(int x,int y)

{

    int lc=lca(x,y);

    return deep[x]+deep[y]-*deep[lc];

}

int main()

{

    n=read(); m=read();

    int x,y,z;

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

    {

        x=read(); y=read();

        add(x,y);

    }

    dfs();

    p=log(n)/log()+;

    for(int j=;j<=p;j++)

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

      fa[i][j]=fa[fa[i][j-]][j-];

    int ans1,ans2,tmp;

    while(m--)

    {

        x=read(); y=read(); z=read();

        lca1=lca(x,y); lca2=lca(x,z); lca3=lca(y,z);

        ans1=lca1; ans2=dis(x,lca1)+dis(y,lca1)+dis(z,lca1);

        tmp=dis(x,lca2)+dis(y,lca2)+dis(z,lca2);

        if(tmp<ans2)

        {

            ans2=tmp;

            ans1=lca2;

        }

        tmp=dis(x,lca3)+dis(y,lca3)+dis(z,lca3);

        if(tmp<ans2)

        {

            ans2=tmp;

            ans1=lca3;

        }

        printf("%d %d\n",ans1,ans2);

    }

}

代码二：算1个lca && 倍增求lca && 读入优化结果：上图第2行

#include<algorithm>

#include<cstdio>

#include<cmath>

#define N 500001

using namespace std;

int n,m,id[N],cnt,fa[N][],p,deep[N],tmp,ans2;

int front[N],next[N*],to[N*],tot;

int lca1,lca2,lca3;

int read()

{

    int x=; char c=getchar();

    while(c<''||c>'') c=getchar();

    while(c>=''&&c<='') { x=x*+c-''; c=getchar();}

    return x;

}

void add(int x,int y)

{

    to[++tot]=y; next[tot]=front[x]; front[x]=tot;

    to[++tot]=x; next[tot]=front[y]; front[y]=tot;

}

void dfs(int x)

{

    id[x]=++cnt;

    for(int i=front[x];i;i=next[i])

     if(to[i]!=fa[x][])

     {

          fa[to[i]][]=x;

          deep[to[i]]=deep[x]+;

          dfs(to[i]);

     }

}

int lca(int x,int y)

{

    if(x==y) return x;

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

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

     if(id[fa[x][i]]>id[y])

      x=fa[x][i];

    return fa[x][];

}

int dis(int x,int y)

{

    int lc=lca(x,y);

    return deep[x]+deep[y]-*deep[lc];

}

int main()

{

    n=read(); m=read();

    int x,y,z;

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

    {

        x=read(); y=read();

        add(x,y);

    }

    dfs();

    p=log(n)/log()+;

    for(int j=;j<=p;j++)

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

      fa[i][j]=fa[fa[i][j-]][j-];

    while(m--)

    {

        x=read(); y=read(); z=read();

        lca1=lca(x,y); lca2=lca(x,z); lca3=lca(y,z);

        if(lca1==lca2) tmp=lca3;

        else if(lca1==lca3) tmp=lca2;

        else tmp=lca1;

        ans2=dis(x,tmp)+dis(y,tmp)+dis(z,tmp);

        printf("%d %d\n",tmp,ans2);

    }

}

代码三：算1个lca && 树链剖分求lca && 读入优化结果：上图第1行

#include<algorithm>

#include<cstdio>

#include<cmath>

#define N 500001

using namespace std;

int n,m,tmp,ans;

int front[N],next[N*],to[N*],tot;

int lca1,lca2,lca3;

int son[N],deep[N],bl[N],fa[N];

int read()

{

    int x=; char c=getchar();

    while(c<''||c>'') c=getchar();

    while(c>=''&&c<='') { x=x*+c-''; c=getchar();}

    return x;

}

void add(int x,int y)

{

    to[++tot]=y; next[tot]=front[x]; front[x]=tot;

    to[++tot]=x; next[tot]=front[y]; front[y]=tot;

}

void dfs1(int x)

{

    son[x]++;

    for(int i=front[x];i;i=next[i])

     if(to[i]!=fa[x])

     {

          fa[to[i]]=x;

          deep[to[i]]=deep[x]+;

          dfs1(to[i]);

          son[x]+=son[to[i]];

     }

}

void dfs2(int x,int top)

{

    bl[x]=top;

    int y=;

    for(int i=front[x];i;i=next[i])

     if(to[i]!=fa[x]&&son[to[i]]>son[y]) y=to[i];

    if(!y) return;

    dfs2(y,top);

    for(int i=front[x];i;i=next[i])

     if(to[i]!=fa[x]&&to[i]!=y) dfs2(to[i],to[i]);

}

int lca(int x,int y)

{

    while(bl[x]!=bl[y])

    {

        if(deep[bl[x]]<deep[bl[y]]) swap(x,y);

        x=fa[bl[x]];

    }

    return deep[x]<deep[y] ? x:y;

}

int dis(int x,int y)

{

    int lc=lca(x,y);

    return deep[x]+deep[y]-*deep[lc];

}

int main()

{

    n=read(); m=read();

    int x,y,z;

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

    {

        x=read(); y=read();

        add(x,y);

    }

    dfs1();

    dfs2(,);

    while(m--)

    {

        x=read(); y=read(); z=read();

        lca1=lca(x,y); lca2=lca(x,z); lca3=lca(y,z);

        if(lca1==lca2) tmp=lca3;

        else if(lca1==lca3) tmp=lca2;

        else tmp=lca1;

        ans=dis(x,tmp)+dis(y,tmp)+dis(z,tmp);

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

    }

}

上图第4行为算3个lca && 倍增求lca

码农公寓