记录编号	326050	评测结果	AAAAAAAAAA
题目名称	[USACO Oct08] 牧场旅行	最终得分	100
用户昵称	kito	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2016-10-20 19:17:21	内存使用	0.34 MiB

#include<cstdio>
using namespace std;
#define	fcl	fclose(stdin);	fclose(stdout);	return 0
	#define	SUBMIT 2333
int n,q;
struct EDGE{
	int to,dis,next;
}edge[2010];
int head[1010],tot=0;
inline void AddEdge(const int& a,const int& b,const int& c){
	edge[++tot].to=b;
	edge[tot].dis=c;
	edge[tot].next=head[a];
	head[a]=tot;
}

int deep[1010],son[1010]={0},prt[1010],size[1010];
bool flag[1010]={false};
int top[1010],w[1010];
void Dfs1(int u){
	size[u]=1;
	flag[u]=true;
	int y;
	for(int x=head[u];x;x=edge[x].next){
		y=edge[x].to;
		if(!flag[y]){
			prt[y]=u;
			deep[y]=deep[u]+1;
			w[y]=w[u]+edge[x].dis;
			Dfs1(y);
			size[u]+=size[y];
			if(size[son[u]]<size[y])	son[u]=y;
		}
	}
}

void Dfs2(int u,int tp){
	top[u]=tp;
	if(son[u]){
		Dfs2(son[u],tp);
	}
	int y;
	for(int x=head[u];x;x=edge[x].next){
		y=edge[x].to;
		if(prt[y]==u&&son[u]!=y){
			Dfs2(y,y);
		}
	}
}

int Lca(int a,int b){
	while(top[a]!=top[b]){
		if(deep[top[a]]<deep[top[b]]){
			b=prt[top[b]];
		}
		else	a=prt[top[a]];
	}
	if(deep[a]<deep[b])	return a;
	return b;
}

void Query(int a,int b){
	int c=Lca(a,b);
	printf("%d\n",w[a]-w[c]+w[b]-w[c]);
}

int main(){
	#ifdef SUBMIT
	freopen("pwalk.in","r",stdin);
	freopen("pwalk.out","w",stdout);
	#endif
	scanf("%d%d",&n,&q);
	int a,b,c;
	for(int i=1;i<n;++i){
		scanf("%d%d%d",&a,&b,&c);
		AddEdge(a,b,c);
		AddEdge(b,a,c);
	}
	deep[1]=1;
	Dfs1(1);
	Dfs2(1,1);
	for(int i=1;i<=q;++i){
		scanf("%d%d",&a,&b);
		Query(a,b);
	}
	#ifndef SUBMIT
	getchar();	getchar();
	#endif
	fcl;
}