这道题还是水题QAQ，因为本蒟蒻一A
题目描述 欢乐岛上有个非常好玩的游戏，叫做“紧急集合”。在岛上分散有N个等待点，有N-1条道路连接着它们，每一条道路都连接某两个等待点，且通过这些道路可以走遍所有的等待点，通过道路从一个点到另一个点要花费一个游戏币。 参加游戏的人三人一组，开始的时候，所有人员均任意分散在各个等待点上（每个点同时允许多个人等待），每个人均带有足够多的游戏币（用于支付使用道路的花费）、地图（标明等待点之间道路连接的情况）以及对话机（用于和同组的成员联系）。当集合号吹响后，每组成员之间迅速联系，了解到自己组所有成员所在的等待点后，迅速在N个等待点中确定一个集结点，组内所有成员将在该集合点集合，集合所用花费最少的组将是游戏的赢家。 小可可和他的朋友邀请你一起参加这个游戏，由你来选择集合点，聪明的你能够完成这个任务，帮助小可可赢得游戏吗？ 输入输出格式 输入格式： 第一行两个正整数N和M（N<=500000，M<=500000），之间用一个空格隔开。分别表示等待点的个数（等待点也从1到N进行编号）和获奖所需要完成集合的次数。 随后有N-1行，每行用两个正整数A和B，之间用一个空格隔开，表示编号为A和编号为B的等待点之间有一条路。 接着还有M行，每行用三个正整数表示某次集合前小可可、小可可的朋友以及你所在等待点的编号。 输出格式： 一共有M行，每行两个数P,C，用一个空格隔开。其中第i行表示第i次集合点选择在编号为P的等待点，集合总共的花费是C个游戏币。 输入输出样例 输入样例#1： 复制 6 4 1 2 2 3 2 4 4 5 5 6 4 5 6 6 3 1 2 4 4 6 6 6 输出样例#1： 复制 5 2 2 5 4 1 6 0 说明 提示： 40%的数据中N<=2000，M<=2000 100%的数据中，N<=500000，M<=500000
这道题呢，就是暴力lca，因为三个点选两个点做lca，然后把他们两个的lca再和第三个点做lca，再算距离就ok了
lca树链剖分还是首选
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define clear(a,val) memset(a,val,sizeof(a)) 5 #define N 500011 6 using namespace std; 7 struct star{int to,nxt;}edge[2*N]; 8 int head[N],son[N],size[N],top[N],idx[N],f[N],dep[N]; 9 int cnt=1,n,m,u,v,w,tt; 10 inline void add(int u,int v) 11 { 12 edge[cnt].nxt=head[u]; 13 edge[cnt].to=v; 14 head[u]=cnt++; 15 } 16 int init(int now,int fa) 17 { 18 size[now]=1; 19 int maxson=-1; 20 for(int i=head[now];i!=-1;i=edge[i].nxt) 21 { 22 int to=edge[i].to; 23 if(to==fa)continue; 24 dep[to]=dep[now]+1,f[to]=now; 25 size[now]+=init(to,now); 26 if(size[to]>maxson)maxson=size[to],son[now]=to; 27 } 28 return size[now]; 29 } 30 void remark(int now,int topf,int fa) 31 { 32 idx[now]=++tt; 33 top[now]=topf; 34 if(!son[now])return; 35 remark(son[now],topf,now); 36 for(int i=head[now];i!=-1;i=edge[i].nxt) 37 { 38 int to=edge[i].to; 39 if((!idx[to]) && to!=fa)remark(to,to,now); 40 } 41 } 42 int ask(int u,int v) 43 { 44 while(top[u]!=top[v]) 45 { 46 if(dep[top[u]]<dep[top[v]])swap(u,v); 47 u=f[top[u]]; 48 } 49 return dep[u]<dep[v]?u:v; 50 } 51 inline int getlen(int u,int v,int ances){return dep[u]-dep[ances]+dep[v]-dep[ances];} 52 inline pair<int,int> getans(int u,int v,int w) 53 { 54 if(u==v &&v==w)return make_pair(u,0); 55 int a=ask(u,v),b=ask(u,w),c=ask(v,w),ans,x=ask(a,w),y=ask(b,v),z=ask(c,u); 56 int aa=getlen(u,v,a)+getlen(a,w,x); 57 int bb=getlen(u,w,b)+getlen(b,v,y); 58 int cc=getlen(v,w,c)+getlen(c,u,z); 59 if(bb<aa){ 60 if(bb<cc)ans=b; 61 else ans=c; 62 }else{ 63 if(aa<cc)ans=a; 64 else ans=c; 65 } 66 return make_pair(ans,min(aa,min(bb,cc))); 67 } 68 int main() 69 { 70 clear(head,-1); 71 scanf("%d%d",&n,&m); 72 for(int i=1;i<n;i++) 73 scanf("%d%d",&u,&v),add(u,v),add(v,u); 74 dep[1]=1; 75 init(1,-1),remark(1,1,-1); 76 for(int i=1;i<=m;i++) 77 scanf("%d%d%d",&u,&v,&w),printf("%d %d ",getans(u,v,w).first,getans(u,v,w).second); 78 return 0; 79 }