就是说给你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]);
    }
}