莫欺少年穷，修魔之旅在这开始—>算法提高课题解

Tarjan算法 + DFS预处理

思路：

1. 先用 dfs 预处理每个点到达 1 号点的距离
2. tarjan算法有三类点：（1）已经回溯的点（2）正在搜索的点（3）还未搜索的点
3. 处理一个正在搜索的点时，枚举他的所有没搜索过的邻点，一直到最里层，然后 p[j] = u;
4. 枚举所有跟这个点有关系的点，最近公共祖先就是另一个点的 find
5. 距离 = 两个点到根节点的距离之和 - 最近公共祖先到根节点距离的两倍

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

const int N = 10010, M = 20010;

int n,m;
int h[N],e[M],w[M],ne[M],idx;
int dist[N];
int p[N];
int st[N];
int res[M];
vector<PII> query[N];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

//预处理每个点到达 1 号点的距离
void dfs(int u,int fa)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j!=fa)
        {
            dist[j]=dist[u]+w[i];
            dfs(j,u);
        }
    }
}

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

void tarjan(int u)
{
    //正在搜索的点
    st[u]=1;

    //枚举这个点的所有的邻点
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            tarjan(j);
            p[j]=u;
        }
    }

    //处理跟这个点有关系的点且该点已经回溯
    for(auto item : query[u])
    {
        int ver=item.first,id=item.second;

        //两点的距离就是他们到根节点的距离之和-两倍的最近公共祖先到根节点的距离
        if(st[ver]==2) res[id]=dist[u]+dist[ver]-dist[find(ver)]*2;
    }

    //表示该点已经回溯
    st[u]=2;
}

int main()
{
    cin>>n>>m;

    memset(h,-1,sizeof h);

    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }

    dfs(1,-1);

    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        query[a].push_back({b,i});
        query[b].push_back({a,i});
    }

    //并查集初始化操作
    for(int i=1;i<=n;i++) p[i]=i;

    tarjan(1);

    for(int i=0;i<m;i++) cout<<res[i]<<endl;

    return 0;
}