题意
给定一个带边权的无根树，求任意三点的最短距离。
解题
设d[u]为节点u到根的距离。
树上任意两点的最短距离为：d[u]+d[v]-2*d[lca].
lca为u和v的最近公共祖先。
将求三点距离转化为求两点距离，容易得到：
x、y、z三点最短距离=（x和y的最短距离+x和z的最短距离+y和z的最短距离）/ 2.
AC代码
//100ms 11.6MB
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>
#include <iostream>
using namespace std;const int maxn=5e4+100;
const int maxm=7e4+100;
int d[maxn];//d[u]表示u结点距根的距离struct edge
{int from,to,w,next,lca;
}e[maxn<<1],q[maxm*6];
int par[maxn],n;
int ance[maxn];
int head[maxn],cnt,first[maxn],tot,vis[maxn];
void add_edge(int u,int v,int w)//树图连边
{e[++cnt].to=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt;
}
void _add(int u,int v)//查询连边，都是单向边
{q[++tot].to=v;q[tot].from=u;q[tot].next=first[u];first[u]=tot;
}
void init()//边以及并查集的初始化
{memset(head,-1,sizeof(head));memset(first,-1,sizeof(first));memset(vis,0,sizeof(vis));for(int i=0;i<=n;i++) par[i]=i;tot=-1;//查询边的编号从0开始cnt=-1;//树图边的编号从0开始
}
int find(int x)//查询祖先结点
{return par[x]==x?x:par[x]=find(par[x]);
}void unit(int x,int y)//合并
{int fx=find(x),fy=find(y);if(fx==fy) return ;par[fx]=fy;
}void tarjan(int u)//dfs+并查集
{vis[u]=1;for(int i=head[u];i!=-1;i=e[i].next){int v=e[i].to;if(vis[v]) continue;d[v]=d[u]+e[i].w;tarjan(v);unit(v,u);}for(int i=first[u];i!=-1;i=q[i].next){int v=q[i].to;if(!vis[v]) continue;q[i].lca=q[i^1].lca=find(v);}
}
int main()
{int m;int kase=0;while(~scanf("%d",&n)){if(kase++) putchar(10);init();for(int i=1; i<n; i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);add_edge(u,v,w);add_edge(v,u,w);}scanf("%d",&m);for(int i=1; i<=m; i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);_add(x,y);//注意查询必须连双向边_add(y,x);_add(x,z);_add(z,x);_add(y,z);_add(z,y);}d[0]=0;tarjan(0);for(int i=0; i<m; i++){int ans=0;int id=i*6,u=q[id].from,v=q[id].to,lca=q[id].lca;ans+=d[u]+d[v]-2*d[lca];id+=2;u=q[id].from,v=q[id].to,lca=q[id].lca;ans+=d[u]+d[v]-2*d[lca];id+=2;u=q[id].from,v=q[id].to,lca=q[id].lca;ans+=d[u]+d[v]-2*d[lca];ans>>=1;printf("%d\n",ans);}}return 0;
}