就是说给你n个点，n-1条边构成一个无向图。
然后还有m次询问，每次问你两个点的最短距离。
于是转换成最短路问题？
嗯，最多有4万个点，边的话算是4万条吧，
于是用spfa的话，每次算一个单源点的最短路，
大概是32*10的8次方时间复杂度，
题目只给了1秒，
所以超时的节奏。
有一个叫做tarjan的算法，
是用来求两个节点的最近公共祖先的，
听说是正常人能写出的求此类方法的最快算法，
反正我是没看懂。
于是这道题可以转换成求最近公共祖先，
求的过程顺便算下每个点到根节点的距离就可以
求这道题了。
tarjan算法的时间渐进复杂度是询问数+图中边的数目，
于是就是8万的样子，不会超时的样子。
那么这个算法怎么写，我觉得是这样的。
它大概是用dfs和并查集实现的，
为了加快访问边的速度，我还用到了链式向前星
这个数据结构。
具体点大概是这样，
从根节点开始搜索，
每次搜索一开始就把当前搜索的那个点
标记为已经加入并查集，
加入并查集就意味着，
这个点已经加入了某棵子树，
这就意味着已经跟某个节点有了最近公共祖先，
至于某点是不是要查询的那个点就不知道了。
怎么求出要查询的两点的最近公共祖先呢？
枚举所有查询，
如果查询两个点中任意一点正好是正在搜索的
那个点，并且另一个点已经加入了某棵子树，
则把这两个点的最近公共祖先设置为此点
与某点的最近公共祖先，
至于为毛这样，不造。
然后搜索所有以这个当前搜索点的为前驱的
没有加入任何子树的后继节点，
直到所有的节点都加入了某棵子树，
这个过程就结束。
好吧，我的代码如下：
#include<iostream>
#include<cstring>
using namespace std;
int num_dot,num_q,num_side,cnt,box[40010],dis[40010],father[40010],vis[40010];
struct node
{
int e,next,w;
}side[80010];
struct node1
{
int s,e,f;
}q[210];
void add(int s,int e,int w)
{
side[cnt].e=e;
side[cnt].w=w;
side[cnt].next=box[s];
box[s]=cnt++;
}
void init()
{
int t1,t2,t3;
cnt=0;
scanf("%d%d",&num_dot,&num_q);
num_side=num_dot-1;
memset(box,-1,sizeof(box));
memset(vis,0,sizeof(vis));
vis[1]=1;
dis[1]=0;
for(int i=0;i<num_side;i++)
{
scanf("%d%d%d",&t1,&t2,&t3);
add(t1,t2,t3);
add(t2,t1,t3);
}
for(int i=0;i<num_q;i++)
scanf("%d%d",&q[i].s,&q[i].e);
}
int find(int x)
{
while(x!=father[x])
x=father[x];
return x;
}
void dfs(int mid)
{
vis[mid]=1;
father[mid]=mid;
for(int i=0;i<num_q;i++)
{
if(q[i].s==mid&&vis[q[i].e])
q[i].f=find(q[i].e);
else if(q[i].e==mid&&vis[q[i].s])
q[i].f=find(q[i].s);
}
for(int i=box[mid];i!=-1;i=side[i].next)
if(!vis[side[i].e])
{
dis[side[i].e]=dis[mid]+side[i].w;
dfs(side[i].e);
father[side[i].e]=mid;
}
}
int main()
{
int exp;
scanf("%d",&exp);
while(exp--)
{
init();
dfs(1);
for(int i=0;i<num_q;i++)
printf("%d\n",dis[q[i].s]+dis[q[i].e]-2*dis[q[i].f]);
}
}