记录编号	251571	评测结果	AAAAAAAAAA
题目名称	[USACO Oct08] 牧场旅行	最终得分	100
用户昵称	Marvolo	是否通过	通过
代码语言	C++	运行时间	0.021 s
提交时间	2016-04-18 13:24:49	内存使用	8.14 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
using namespace std;

int n,q,x,y,i,j;
int f[1010],fa[1010],w[1010],ww[1010];
bool v[1010];
int l[1010][1010],lca[1010][1010];
vector<int> b[1010],son[1010];

void maketree(int p){
	int i;
	v[p]=true;
	if (b[p].size()==0)	return;
	for (i=0;i<=b[p].size()-1;i++)
	if (v[b[p][i]]==false)	{
		f[b[p][i]]=p;		
		son[p].push_back(b[p][i]);
		maketree(b[p][i]);
	}
	return;
}			//	DFS建树 

void ready(){
	int i;
	for (i=1;i<=n;i++){
	b[i].clear();	v[i]=false;	fa[i]=i;		}
	return;
}			//	预处理 

int find(int x){
	if (fa[x]==x)	return x;
	else {	fa[x]=find(fa[x]);return fa[x];}
}

void tarjan(int p){
	int i,q,w;
	if (son[p].size()!=0)	{
		for (i=0;i<=son[p].size()-1;i++)
			if (!v[son[p][i]]){
			tarjan(son[p][i]);
			fa[son[p][i]]=p;
				}
	}
	v[p]=true;
	
	if (b[p].size()!=0)		
	for (i=0;i<=b[p].size()-1;i++)
	if (v[b[p][i]])	{
	lca[p][b[p][i]]=find(b[p][i]);
	lca[b[p][i]][p]=find(b[p][i]);
	}
	
	return;
}			//	Tarjan求LCA 

void answer(int p,int q,int lc){
	int e,u,ans;
	e=p;	u=q;	ans=0; 
	while (e!=lc){
	ans+=l[e][f[e]];
	e=f[e];
	}
	while (u!=lc){
	ans+=l[u][f[u]];
	u=f[u];
	}
	printf("%d\n",ans);
	return;	
}			//	计算距离 

int main(){
	freopen("pwalk.in","r",stdin);
	freopen("pwalk.out","w",stdout);
	scanf("%d%d",&n,&q);
	
	for (i=1;i<=n-1;i++){
		scanf("%d%d",&x,&y);
		scanf("%d",&l[x][y]);
		l[y][x]=l[x][y];
		b[x].push_back(y);	b[y].push_back(x);
	}
	f[1]=1;
	maketree(1);
	ready();
	for (i=1;i<=q;i++){
	scanf("%d%d",&w[i],&ww[i]);
	b[w[i]].push_back(ww[i]);	b[ww[i]].push_back(w[i]);
		}
	fa[1]=1;
	tarjan(1);
	 
	for (i=1;i<=q;i++)
	answer(w[i],ww[i],lca[w[i]][ww[i]]);
	return 0;
}