Lvat_s Blog

颓废了2个晚上，总算水掉了这道题……

这题我们使用倍增LCA可以解决。

每次三个点找两点间LCA，相同的LCA取另一个就可以了。

我没有使用读入优化，如果用了速度会更快吧……

#include<cstdio>

int n,m,h[500005],en,fa[500005][20],deep[500005],flg[500005];

struct Edge{
int b,next;
}e[1000005];

void add(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}

void Yuchuli(int u){
flg[u]=1;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(!flg[v]){
        deep[v]=deep[u]+1;
        fa[v][0]=u;
        Yuchuli(v);
    }
}
}

void Move(int &u,int H){
for(int i=18;i>=0;i--){
    if(deep[fa[u][i]]>=H){
        u=fa[u][i];
    }
}
}

int LCA(int u,int v){
int now=0;
if(deep[u]!=deep[v]){if(deep[u]>deep[v])Move(u,deep[v]);else Move(v,deep[u]);}
if(u==v){return u;}
for(int i=18;i>=0;i--){
    if(fa[u][i]!=fa[v][i]){
        u=fa[u][i];
        v=fa[v][i];
    }
}
return fa[u][0];
}

int GetCost(int u,int v){
int w=LCA(u,v);
return deep[u]+deep[v]-2*deep[w];
}

int main(){
freopen("1787.in","r",stdin);
freopen("1787.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<n;i++){
    int sa,sb;
    scanf("%d %d",&sa,&sb);
    add(sa,sb);
    add(sb,sa);
}
Yuchuli(1);
fa[1][0]=1;
for(int j=1;j<=18;j++){
    for(int i=1;i<=n;i++){
        fa[i][j]=fa[fa[i][j-1]][j-1];
    }
}
while(m--){
    int sa,sb,sc;
    scanf("%d %d %d",&sa,&sb,&sc);
    int FineLCA,LCA1=LCA(sa,sb),LCA2=LCA(sa,sc),LCA3=LCA(sb,sc);
    if(LCA1==LCA2)FineLCA=LCA3;
    else if(LCA3==LCA2)FineLCA=LCA1;
    else FineLCA=LCA2;
    printf("%d %d\n",FineLCA,GetCost(FineLCA,sa)+GetCost(FineLCA,sb)+GetCost(FineLCA,sc));
}
return 0;
}

upd 2016.6.2

今天学习了Tarjan求LCA，用这个题练习一下

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=500005,INF=2100000000;

int n,m,h[N],en,f[N],vis[N],dep[N],anc[N];

struct Edge{
int b,next;
}e[N<<1];

struct List{
int v,par;
List *next;
List(){next=NULL;par=0;}
List(int _v,List *_next){v=_v;next=_next;par=0;}
}*Lis[N];

List *AddList(int u,int v){
List *node=new List(v,Lis[u]);
Lis[u]=node;
return node;
}

struct Query{
int u,v,w;
List *id11,*id12,*id21,*id22,*id31,*id32;
Query(){}
Query(int _u,int _v,int _w){u=_u;v=_v;w=_w;}
}Que[N];

void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}

int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
int Abs(int x){return x>0?x:-x;}
int GetCost(int u,int v,int w){return dep[u]+dep[v]-2*dep[w];}

void Tarjan(int u,int fa){
f[u]=u;
dep[u]=dep[fa]+1;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(!f[v]){Tarjan(v,u);f[v]=u;}
}
for(List *I=Lis[u];I;I=I->next){
    int v=I->v;
    if(f[v])I->par=Find(v);
}
}

int main(){
freopen("1787.in","r",stdin);
freopen("1787.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<n;i++){
	int u,v;
	scanf("%d %d",&u,&v);
	AddEdge(u,v);AddEdge(v,u);
}
for(int i=1;i<=m;i++){
	scanf("%d %d %d",&Que[i].u,&Que[i].v,&Que[i].w);
	Que[i].id11=AddList(Que[i].u,Que[i].v);
	Que[i].id21=AddList(Que[i].u,Que[i].w);
	Que[i].id31=AddList(Que[i].v,Que[i].w);
	Que[i].id12=AddList(Que[i].v,Que[i].u);
	Que[i].id22=AddList(Que[i].w,Que[i].u);
	Que[i].id32=AddList(Que[i].w,Que[i].v);
}
Tarjan(1,1);
for(int i=1;i<=m;i++){
    int LCA1=max(Que[i].id11->par,Que[i].id12->par);
    int LCA2=max(Que[i].id21->par,Que[i].id22->par);
    int LCA3=max(Que[i].id31->par,Que[i].id32->par);
    int Cost=GetCost(LCA1,Que[i].u,LCA1)+GetCost(LCA1,Que[i].v,LCA1)+GetCost(LCA1,Que[i].w,LCA2);
    if(LCA1==LCA2){Cost=GetCost(LCA3,Que[i].u,LCA2)+GetCost(LCA3,Que[i].v,LCA3)+GetCost(LCA3,Que[i].w,LCA3);LCA1=LCA3;}
    else if(LCA1==LCA3){Cost=GetCost(LCA2,Que[i].u,LCA2)+GetCost(LCA2,Que[i].v,LCA1)+GetCost(LCA2,Que[i].w,LCA2);LCA1=LCA2;}
	printf("%d %d\n",LCA1,Cost);
}
return 0;
}