记录编号	597256	评测结果	AAAAAAAAAA
题目名称	距离	最终得分	100
用户昵称	djyqjy	是否通过	通过
代码语言	C++	运行时间	0.233 s
提交时间	2024-11-25 20:52:10	内存使用	4.60 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int ver[2*N],edge[2*N],nxt[2*N],hd[N];
int jsq=1;
void add_edge(int x,int y,int val)
{
	ver[++jsq]=y;
	edge[jsq]=val;
	nxt[jsq]=hd[x];
	hd[x]=jsq;
	return;
}
int n,q;
int f[N][16],depth[N],len[N];
void dfs(int x,int fa)
{
	depth[x]=depth[fa]+1;
	f[x][0]=fa;
	for(int i=1;i<=14;i++)
	    f[x][i]=f[f[x][i-1]][i-1];
	for(int i=hd[x];i;i=nxt[i])
	{
		int y=ver[i];
		if(y==fa) continue;
		len[y]=len[x]+edge[i];
		dfs(y,x);
	}
	return;
}
int lca(int a,int b)
{
	if(depth[a]>depth[b]) swap(a,b);
	for(int i=14;i>=0;i--)
	    if(depth[f[b][i]]>=depth[a]) b=f[b][i];
	if(a==b) return a;
	for(int i=14;i>=0;i--)
	    if(f[a][i]!=f[b][i]) a=f[a][i],b=f[b][i];
	return f[a][0];
}
int main()
{
	freopen("distance.in","r",stdin);
	freopen("distance.out","w",stdout);
	scanf("%d%d",&n,&q);
	for(int i=1,x,y,z;i<n;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		add_edge(x,y,z);
		add_edge(y,x,z);
	}
	dfs(1,0);
	for(int x,y;q;q--)
	{
		scanf("%d%d",&x,&y);
		printf("%d\n",len[x]+len[y]-2*len[lca(x,y)]);
	}
	return 0;
}