记录编号	458593	评测结果	AAAAAAAAAA
题目名称	[USACO Oct08] 牧场旅行	最终得分	100
用户昵称	Lovelove_boii	是否通过	通过
代码语言	C++	运行时间	0.032 s
提交时间	2017-10-11 16:36:33	内存使用	5.11 MiB

#include<fstream>
using namespace std;
ifstream cin("pwalk.in");
ofstream cout("pwalk.out");
struct node
{
	int father,value;
}tree[1001];
int n,q;
int union_find[1001];
int ask[1001][2];
bool que[1001][1001];
int ans[1001][1001];
int root;
bool vis[1001];
int Find(int x)
{
	if(x==union_find[x])
	{
		return x;
	}
	return Find(union_find[x]);
}
void Union(int tar,int get)
{
	union_find[get]=Find(tar);
}
int get_ans(int s,int t,int lca)
{
	int ret=0;
	while(s!=lca)
	{
		ret+=tree[s].value;
		s=tree[s].father;
	}
	while(t!=lca)
	{
		ret+=tree[t].value;
		t=tree[t].father;
	}
	return ret;
}
void tarjan(int r)
{
	for(int i=1;i<=n;i++)
	{
		if(tree[i].father==r)
		{
			tarjan(i);
			Union(r,i);
			vis[i]=true;
		}
	}
	for(int i=1;i<=1000;i++)
	{
		if(que[r][i])
		{
			if(vis[i])
			{
				int lca=Find(i);
				ans[r][i]=ans[i][r]=get_ans(r,i,lca);
			}
		}
	}
	return;
}
int main()
{
	cin>>n>>q;
	for(int i=1;i<n;i++)
	{
		union_find[i]=i;
		int u,v,val;
		cin>>u>>v>>val;
		tree[u].father=v;
		tree[u].value=val;
	}
	union_find[n]=n;
	for(int i=1;i<=n;i++)
	{
		if(!tree[i].father)
		{
			root=i;
		}
	}
	for(int i=1;i<=q;i++)
	{
		int p1,p2;
		cin>>p1>>p2;
		ask[i][0]=p1;
		ask[i][1]=p2;
		que[p1][p2]=que[p2][p1]=true;
	}
	tarjan(root);
	for(int i=1;i<=q;i++)
	{
		cout<<ans[ask[i][0]][ask[i][1]]<<endl;
	}
	cin.close();
	cout.close();
	return 0;
}