tarjan

#include<bits/stdc++.h>
using namespace std;
int n,q,rt,ans[100001];
//n:点数 q:问题数 rt:根  ans[i]:第i个问题的结果
struct upp{
	int tu,yu;
};
vector<upp> e[100001];//问题记录 
vector<upp> a[100001];
int de[100001];//距根节点距离 
int fa[100001];
int fi(int x)
{
    if(fa[x]==x)
        return x;
    return fa[x]=fi(fa[x]);
}
void sbga(int n,int u,int f)//n:这一个 u:上一个 f:距顶点距离 
{
	de[n]=f;//记录n距根节点距离 
	for(int i=0;i<e[n].size();i++) 
	{
		int too=e[n][i].tu;//n --> too 
		int nowe=e[n][i].yu;//nowe：问题编号 
		if(de[too]!=-1)
		{
			int w=fi(too);
			if(ans[nowe]==-1)
				ans[nowe]=de[n]+de[too]-2*de[w];
		}
	}
	for(int i=0;i<a[n].size();i++)
	{
		int nxt=a[n][i].tu;// nxt：下一个 
		int nxfar=a[n][i].yu;//nxfar:距下一个距离 
		if(nxt==u)
			continue;
		if(de[nxt]==-1)
			sbga(nxt,n,f+nxfar);
		fa[nxt]=n;
	}
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n-1;i++)
    {
    	int x,y,z;
    	cin>>x>>y>>z;
    	a[x].push_back((upp){y,z});
    	a[y].push_back((upp){x,z});
    	rt=y;
	}
	memset(de,-1,sizeof(de));
	memset(ans,-1,sizeof(ans));
	de[rt]=0;
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<=q;i++)
	{
		int x,y;
		cin>>x>>y;
		if(x==y)
			ans[i]=0;
		e[x].push_back((upp){y,i});
		e[y].push_back((upp){x,i});
	}
	sbga(rt,0,0);
	for(int i=1;i<=q;i++)
		cout<<ans[i]<<"\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10000;
const int MAXQ = 20000;
int n, q, root; // 点数、询问个数、根节点
struct Edge
{
    int v, w;
};
vector<Edge> e[MAXN + 5]; // 存树
int fa[MAXN + 5];
int maxDep, dep[MAXN + 5];
int len[MAXN + 5];
void dfs(int u, int father)
{
    fa[u] = father;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i].v;
        int w = e[u][i].w;
        if (v == father)
            continue;
        dep[v] = dep[u] + 1;
        len[v] = len[u] + w;
        maxDep = max(maxDep, dep[v]);
        dfs(v, u);
    }
}
int lg2[MAXN + 5]; // 替代 log2(i)
int dp[MAXN][35];  // i号点的 2^j 层祖先
int lca(int u, int v)
{
    if (dep[u] > dep[v])
        swap(u, v); // 让u的高度不低于v
    if (u == v)
        return u;
    // 把 v 提到与 u 同样高度
    for (int j = lg2[n]; j >= 0; j--)
        if ((1 << j) <= dep[v] - dep[u])
        {
            v = dp[v][j];
        }
    if (u == v)
        return u;
    // 找lca
    for (int j = lg2[n]; j >= 0; j--)
        if (dp[v][j] != dp[u][j])
        {
            v = dp[v][j],
            u = dp[u][j];
        }
    return dp[u][0];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //  输入
    cin >> n >> q;
    root = 1;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back((Edge){v, w});
        e[v].push_back((Edge){u, w});
    }
    // 预处理：最大层数 maxDep、每个点的深度、记录父节点、log2[]、dp数组
    dep[root] = 0;
    len[root] = 0;
    maxDep = 1;
    dfs(root, 0);
    lg2[1] = 0;
    for (int i = 2; i <= n; i++)
        // i == 2^(log2(i-1)+1)
        if (i == (1 << (lg2[i - 1] + 1)))
            lg2[i] = lg2[i - 1] + 1;
        else
            lg2[i] = lg2[i - 1];
    for (int j = 0; j <= lg2[n]; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            // 求解 dp[i][j]
            if (j == 0)
                dp[i][j] = fa[i];
            else
                dp[i][j] = dp[dp[i][j - 1]][j - 1];
        }
    }
    // q 次询问
    while (q--)
    {
        int u, v;
        cin >> u >> v; // 求 lca(u,v)
        cout << len[u] + len[v] - 2 * len[lca(u, v)] << "\n";
    }
    return 0;
}