颓废了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;
}
