「BZOJ1787」[Ahoi2008] Meet 紧急集合

2014年5月7日5,4232

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

题解

忘记换行搞半天我擦咧

求三个结点到一个结点距离之和最小的结点以及距离和

求出两两lca，其中有两个相同，答案则为另一个，画画图就可以理解

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}
int n,q,cnt;
int deep[500001],head[500001],fa[500001][20];
bool vis[500001];
struct data{int to,next;}e[1000001];
void ins(int u,int v)
{e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;}
void insert(int u,int v)
{ins(u,v);ins(v,u);}
void dfs(int x)
{
    vis[x]=1;
    for(int i=1;i<=18;i++)
    {
        if(deep[x]<(1<<i))break;
        fa[x][i]=fa[fa[x][i-1]][i-1];
    }
    for(int i=head[x];i;i=e[i].next)
    {
        if(vis[e[i].to])continue;
        deep[e[i].to]=deep[x]+1;
        fa[e[i].to][0]=x;
        dfs(e[i].to);
    }
}
int lca(int x,int y)
{
    if(deep[x]<deep[y])swap(x,y);
    int d=deep[x]-deep[y];
    for(int i=0;i<=18;i++)
       if((1<<i)&d)x=fa[x][i];
    for(int i=18;i>=0;i--)
       if(fa[x][i]!=fa[y][i]) 
          {x=fa[x][i];y=fa[y][i];}
    if(x==y)return x;
    else return fa[x][0];
}
int dis(int x,int y){int t=lca(x,y);return deep[x]+deep[y]-2*deep[t];}
int cal(int x,int y,int z)
{
	int p1=lca(x,y),p2=lca(x,z),p3=lca(y,z),t;
	if(p1==p2)t=p3;
	else if(p2==p3)t=p1;
	else t=p2;
	int ans;
	ans=dis(x,t)+dis(y,t)+dis(z,t);
	printf("%d %d\n",t,ans);
}
int main()
{
    n=read();q=read();
    for(int i=1;i<n;i++)
    {
        int u,v,w;
        u=read();v=read();
        insert(u,v);
    }
    dfs(1);
    for(int i=1;i<=q;i++)
    {
        int x,y,z;
        x=read();y=read();z=read();
        cal(x,y,z);
    }
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

using namespace std;

inline int read()

{

char ch=getchar();

int f=1,x=0;

while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}

return x*f;

}

int n,q,cnt;

int deep[500001],head[500001],fa[500001][20];

bool vis[500001];

struct data{int to,next;}e[1000001];

void ins(int u,int v)

{e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;}

void insert(int u,int v)

{ins(u,v);ins(v,u);}

void dfs(int x)

{

vis[x]=1;

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

{

if(deep[x]<(1<<i))break;

fa[x][i]=fa[fa[x][i-1]][i-1];

}

for(int i=head[x];i;i=e[i].next)

{

if(vis[e[i].to])continue;

deep[e[i].to]=deep[x]+1;

fa[e[i].to][0]=x;

dfs(e[i].to);

}

int lca(int x,int y)

{

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

int d=deep[x]-deep[y];

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

if((1<<i)&d)x=fa[x][i];

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

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

{x=fa[x][i];y=fa[y][i];}

if(x==y)return x;

else return fa[x][0];

}

int dis(int x,int y){int t=lca(x,y);return deep[x]+deep[y]-2*deep[t];}

int cal(int x,int y,int z)

{

int p1=lca(x,y),p2=lca(x,z),p3=lca(y,z),t;

if(p1==p2)t=p3;

else if(p2==p3)t=p1;

else t=p2;

int ans;

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

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

}

int main()

{

n=read();q=read();

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

{

int u,v,w;

u=read();v=read();

insert(u,v);

}

dfs(1);

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

{

int x,y,z;

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

cal(x,y,z);

}

return 0;

}

或者将三个lca分别计算取最优

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#define inf 0x7fffffff
using namespace std;
inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}
int n,q,cnt;
int deep[500001],head[500001],fa[500001][20];
bool vis[500001];
struct data{int to,next;}e[1000001];
void ins(int u,int v)
{e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;}
void insert(int u,int v)
{ins(u,v);ins(v,u);}
void dfs(int x)
{
    vis[x]=1;
    for(int i=1;i<=18;i++)
    {
        if(deep[x]<(1<<i))break;
        fa[x][i]=fa[fa[x][i-1]][i-1];
    }
    for(int i=head[x];i;i=e[i].next)
    {
        if(vis[e[i].to])continue;
        deep[e[i].to]=deep[x]+1;
        fa[e[i].to][0]=x;
        dfs(e[i].to);
    }
}
int lca(int x,int y)
{
    if(deep[x]<deep[y])swap(x,y);
    int t=deep[x]-deep[y];
    for(int i=0;i<=18;i++)
       if(t&(1<<i))x=fa[x][i];
    for(int i=18;i>=0;i--)
       if(fa[x][i]!=fa[y][i])
       {x=fa[x][i];y=fa[y][i];}
    if(x==y)return x;
    return fa[x][0];
}
int cal(int x,int y,int z)
{
	int p1=lca(x,y),p2=lca(x,z),p3=lca(y,z),ans=inf,tmp,t;
	int q1=lca(p1,z),q2=lca(p2,y),q3=lca(p3,x);
	tmp=deep[x]+deep[y]-deep[p1]+deep[z]-2*deep[q1];
	if(tmp<ans){ans=tmp;t=p1;}
	tmp=deep[x]+deep[z]-deep[p2]+deep[y]-2*deep[q2];
	if(tmp<ans){ans=tmp;t=p2;}
	tmp=deep[y]+deep[z]-deep[p3]+deep[x]-2*deep[q3];
	if(tmp<ans){ans=tmp;t=p3;}
	printf("%d %d\n",t,ans);
}
int main()
{
    n=read();q=read();
    for(int i=1;i<n;i++)
    {
        int u,v;
        u=read();v=read();
        insert(u,v);
    }
    dfs(1);
    for(int i=1;i<=q;i++)
    {
        int x,y,z;
        x=read();y=read();z=read();
        cal(x,y,z);
    }
    return 0;
}