有关概念：
最近公共祖先（LCA，Lowest Common Ancestors）：对于有根树T的两个结点u、v，最近公共祖先表示u和v的深度最大的共同祖先。
Tarjan是求LCA的离线算法（先存储所有询问，再进行运算）
思路：
从根结点开始DFS，对遍历到的结点u标记已访问，创建新集合，元素为u，再遍历u的每一个儿子，回溯时将每个儿子的集合并到u的集合上，用并查集记录集合中的每个元素的fa为u，接着处理询问，对于关于u的每一个询问，若另一个结点v已访问，则可断定LCA(u,v)为fav，记录结果，最后按顺序输出即可
dis存储该结点到根结点的距离，用于计算两点之间的路径长度
样例推导（样例来自@SHHHS）：
求8、6，9、7的LCA
从根结点1进入，标记访问，创建集合
访问2、4，回溯到2，新集合包含两个结点
访问5、8，处理8的询问，但6未访问，跳过
访问9，处理询问，7未访问，跳过，5、8和9并入2的集合（即fa值设为2）
访问6，处理询问，LCA(8,6)为fa8，即2
访问10，回溯，并入6的集合
回溯，并入2的集合
并入1的集合
访问3、7，处理询问，LCA(7,9)为fa9，即1
回溯，并入3的集合
并入1的集合
#include<cstdio>
#define MAXN
#define MAXQ
int n,Q,heade[MAXN],headq[MAXN],fa[MAXN],lca[MAXQ],dis[MAXN],cnt;
bool vis[MAXN];
struct edge
{
int v,next,val;
}e[MAXN*];
struct query
{
int u,v,next;
}q[MAXQ*];
void adde(int x,int y,int z)
{
e[++cnt].v=y;
e[cnt].next=heade[x];
heade[x]=cnt;
e[cnt].val=z;
}
void addq(int x,int y)
{
q[++cnt].u=x;
q[cnt].v=y;
q[cnt].next=headq[x];
headq[x]=cnt;
}
int getfa(int x)//并查集路径压缩
{
return fa[x]=x==fa[x]?x:getfa(fa[x]);
}
int getdis(int i)//计算路径长度
{
return dis[q[i<<].u]+dis[q[i<<].v]-*dis[lca[i]];
}
void Tarjan(int u)
{
fa[u]=u;
vis[u]=true;
for(int i=heade[u];i;i=e[i].next)
{
int v=e[i].v;
if(!vis[v])
{
dis[v]=dis[u]+e[i].val;
Tarjan(v);
fa[v]=u;
}
}
for(int i=headq[u];i;i=q[i].next)//处理询问
{
int v=q[i].u==u?q[i].v:q[i].u;
if(vis[v])lca[i>>]=getfa(fa[v]);
}
}
int main()
{
scanf("%d",&n);
int x,y,z;
for(int i=;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
adde(x,y,z);
adde(y,x,z);
}
cnt=;
scanf("%d",&Q);
for(int i=;i<=Q;i++)
{
scanf("%d%d",&x,&y);
addq(x,y);
addq(y,x);
}
Tarjan();
for(int i=;i<=Q;i++)
{
printf("%d\n",getdis(i));
}
return ;
}