LCA，对于每一个(x,y,z)，两两求LCA得最优解或求出LCA不同于其他两组的那个为最优解。
code：
/************************************************************** Problem: 1787 User: yekehe Language: C++ Result: Accepted Time:5212 ms Memory:51604 kb ****************************************************************/ #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int read() { char c;while(c=getchar(),c<'0'||c>'9'); int x=c-'0';while(c=getchar(),c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0'; return x; } const int MAXN=500005; int N,M; int head[MAXN],to[MAXN<<1],nxt[MAXN<<1],cnt; void add(int x,int y) { to[cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; cnt++; } int D[MAXN]; int f[20][MAXN]; void dfs(int now,int deep,int fa) { D[now]=deep; f[0][now]=fa; for(int i=head[now];i!=-1;i=nxt[i]) if(!D[to[i]]) dfs(to[i],deep+1,now); return ; } int Me; int get(int x,int y) { if(D[x]<D[y])swap(x,y); for(int i=19;i>=0;i--) if(D[f[i][x]]>=D[y])x=f[i][x]; if(x==y)return x; for(int i=19;i>=0;i--) if(f[i][x]!=f[i][y]) x=f[i][x],y=f[i][y]; return f[0][x]; } int solve(int x,int y) { return D[x]+D[y]-(D[get(x,y)]<<1); } int main(){ memset(head,-1,sizeof head); memset(nxt,-1,sizeof nxt); N=read(),M=read(); register int i,j; for(i=1;i<N;i++){ int x=read(),y=read(); add(x,y),add(y,x); } dfs(1,1,0); for(i=1;i<=19;i++) for(j=1;j<=N;j++) f[i][j]=f[i-1][f[i-1][j]]; for(i=1;i<=M;i++){ int x=read(),y=read(),z=read(); int a=get(x,y),b=get(y,z),c=get(x,z); int dist=0; if(a==b)dist=c;else if(b==c)dist=a;else dist=b; printf("%d %d ",dist,solve(x,dist)+solve(y,dist)+solve(z,dist)); } return 0; }