题意：
给个树，每次给三个点，求与这三个点距离最小的点。
题解：
倍增求出两两之间的LCA后，比较容易理解的做法是挑出两个LCA再做一次LCA，比较所有挑法。但画kan出ti图jie可知其中有两个LCA是相等的，而所求就是那个与它们不等的LCA（我也不知为什么）。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 500500
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std; inline int read(){
char ch=getchar(); int f=,x=;
while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();} while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return x*f;
}
int fa[maxn][],dep[maxn];
struct e{int t,n;}; e es[maxn*]; int g[maxn],ess;
void pe(int f,int t){
es[++ess]=(e){t,g[f]}; g[f]=ess; es[++ess]=(e){f,g[t]}; g[t]=ess;
}
void init(){ess=; memset(g,,sizeof(g));}
void dfs(int x,int f){
for(int i=g[x];i;i=es[i].n)if(es[i].t!=f){
dep[es[i].t]=dep[x]+; fa[es[i].t][]=x; dfs(es[i].t,x);
}
}
int n,m;
void build(){
for(int j=;(<<j)<=n;j++)inc(i,,n)fa[i][j]=fa[fa[i][j-]][j-];
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y); int t=dep[x]-dep[y];
for(int i=;(<<i)<=n;i++)if(t&(<<i))x=fa[x][i];
for(int i=;i>=;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
if(x==y)return x;else return fa[x][];
}
int dis(int x,int y){
int z=lca(x,y); return dep[x]-dep[z]+dep[y]-dep[z];
}
int main(){
n=read(); m=read(); init(); inc(i,,n-){int a=read(),b=read(); pe(a,b);}
dep[]=; fa[][]=; dfs(,); build();
inc(i,,m){
int a=read(),b=read(),c=read(); int x=lca(a,b),y=lca(a,c),z=lca(b,c);
if(x==y)printf("%d %d\n",z,dis(a,z)+dis(b,z)+dis(c,z));
else if(x==z)printf("%d %d\n",y,dis(a,y)+dis(b,y)+dis(c,y));
else if(y==z)printf("%d %d\n",x,dis(a,x)+dis(b,x)+dis(c,x));
}
return ;
}
20160603