本来觉得这是一道挺水的题目，后来觉得出题人挺变态的= =
半个小时敲完后，内存超限它给我看TLE，还是0ms，后来才发现内存限制64m
然后卡了一个小时后AC了。。
题目大意是在一棵树上找三点的最短路
依次挑两个点求LCA，再将LCA与第三个点再求LCA
求三次取最优就行了。
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 using namespace std; 5 const int maxn = 500010; 6 struct node{ 7 int to,next; 8 }e[1000010]; 9 int sum,n,m,tot,logn,l,r,a,b,c,x,y,id; 10 int head[maxn],fa[maxn][21],dep[maxn]; 11 12 void insert(int u, int v, int c){ 13 e[++tot].to=v; 14 //e[tot].cost=c; 15 e[tot].next=head[u]; 16 head[u]=tot; 17 } 18 19 void dfs(int u, int f, int d){ 20 dep[u]=d; 21 fa[u][0]=f; //dis[u][0]=c; 22 for (int i=1; i<=logn; i++) fa[u][i]=fa[fa[u][i-1]][i-1]; 23 //for (int i=1; i<=logn; i++) dis[u][i]=dis[u][i-1]+dis[fa[u][i-1]][i-1]; 24 for (int i=head[u]; i!=-1; i=e[i].next) 25 if (e[i].to!=f) 26 dfs(e[i].to,u,d+1); 27 } 28 29 int lca(int u, int v){ 30 if (dep[u]>dep[v]) swap(u,v); 31 while (dep[u]<dep[v]){ 32 for (int i=logn; i>=0; i--) 33 if (dep[u]<dep[fa[v][i]]){ 34 //sum+=dis[v][i]; 35 v=fa[v][i]; 36 } 37 //sum+=dis[v][0]; 38 v=fa[v][0]; 39 } 40 if (u==v) return u; 41 for (int i=logn; i>=0; i--) 42 if (fa[u][i]!=fa[v][i]){ 43 // sum+=dis[v][i]+dis[u][i]; 44 u=fa[u][i]; v=fa[v][i]; 45 } 46 //sum+=dis[v][0]+dis[u][0]; 47 u=fa[u][0]; v=fa[v][0]; 48 return u; 49 } 50 51 int main(){ 52 scanf("%d%d", &n, &m); 53 tot=-1; 54 for (int i=1; i<=n; i++) head[i]=-1; 55 //memset(head,-1,sizeof(head)); 56 //memset(dis,0,sizeof(dis)); 57 //memset(e,0,sizeof(e)); 58 for (int i=1; i<n; i++){ 59 scanf("%d%d", &l, &r); 60 insert(l,r,1); 61 insert(r,l,1); 62 } 63 logn=0; 64 while ((1<<logn)<n) logn++; 65 dfs(1,0,1); 66 for (int i=1; i<=m; i++){ 67 scanf("%d%d%d", &a, &b, &c); 68 int ans=1000001000; 69 x=lca(a,b); y=lca(x,c); 70 sum=dep[a]+dep[b]+dep[c]-dep[x]-dep[y]*2; 71 if (sum<ans){ 72 ans=sum; 73 id=x; 74 } 75 x=lca(a,c); y=lca(x,b); 76 sum=dep[a]+dep[b]+dep[c]-dep[x]-dep[y]*2; 77 if (sum<ans){ 78 ans=sum; 79 id=x; 80 } 81 x=lca(b,c); y=lca(x,a); 82 sum=dep[a]+dep[b]+dep[c]-dep[x]-dep[y]*2; 83 if (sum<ans){ 84 ans=sum; 85 id=x; 86 } 87 printf("%d %d ", id, ans); 88 } 89 return 0; 90 }