记录编号	537339	评测结果	AAAAAAAAAA
题目名称	[USACO Oct08] 牧场旅行	最终得分	100
用户昵称	leon	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2019-07-11 13:55:14	内存使用	0.00 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=400100;
struct Edge{
	int to,next,dis;
}e[maxn*2];
int f[maxn][20],c[maxn][20],deep[maxn],head[maxn];
long long dis[maxn];
void add(int,int,int);
void Dfs(int,int);
int Lca(int,int);
int len,Deep;
int Main();
int start=Main();
int Main(){
	freopen("pwalk.in","r",stdin);
	freopen("pwalk.out","w",stdout);
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);add(y,x,z);
	}
	f[1][0]=1;
	Dfs(1,1);
	Deep=20;
	for(int j=1;j<=Deep-1;j++){
		for(int i=1;i<=n;i++){
			f[i][j]=f[f[i][j-1]][j-1];
		}
	}
	for(int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		int k=Lca(x,y);
		printf("%d\n",dis[x]+dis[y]-2*dis[k]);
	}
	return 0;
}
void add(int x,int y,int z){
	len++;
	e[len].to=y;
	e[len].dis=z;
	e[len].next=head[x];
	head[x]=len;
}
void Dfs(int x,int dep){
	deep[x]=dep; Deep=max(Deep,dep);
	for(int i=head[x];i;i=e[i].next){
		int j=e[i].to;
		if(!f[j][0]){
			f[j][0]=x; dis[j]=dis[x]+e[i].dis;
			Dfs(j,dep+1);
		}
	}
}
int Lca(int x,int y){
	if(deep[x]<deep[y]) swap(x,y);
	for(int j=Deep-1;j>=0;j--){
		if(deep[f[x][j]]>=deep[y]) x=f[x][j];
	}
	if(x==y) return x;
	for(int j=Deep-1;j>=0;j--){
		if(f[x][j]!=f[y][j]){
			x=f[x][j]; y=f[y][j];
		}
	}
	return f[x][0];
}
int main(){;}