记录编号	467241	评测结果	AAAAAAAAAA
题目名称	距离	最终得分	100
用户昵称	@@@	是否通过	通过
代码语言	C++	运行时间	1.302 s
提交时间	2017-10-30 11:23:30	内存使用	0.75 MiB

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n,m;
int b[10002];
int w[10002];

int ans[10002];
bool out[10002];
;// son

struct N
{
	int to,dis;
}A,B,father[10002];
vector<N> v[10003];
vector<N> question[10003];// son
bool book[10003];
void build(int x)
{
	
	for(int i = 0;i < v[x].size();i++)
	{
		if(v[x][i].to == father[x].to)
		{
			continue;
		}
		father[v[x][i].to].to = x;
		father[v[x][i].to].dis = v[x][i].dis;
		build(v[x][i].to);
	}
}
int find(int x)
{
	if(b[x] == x)
		return x;
	else
		return b[x] = find(b[x]);
}
void Union(int a_,int b_)
{
	int x = find(a_);
	int y = find(b_);
	if(x != y)
	{
		b[y] = x;
	}
}
int LCA(int x,int y)
{
	int ans = 0;
	int z = find(y);
	while(x != z)
	{
		ans += father[x].dis;
		x = father[x].to;
	}
	while(y != z )
	{
		ans += father[y].dis;
		y = father[y].to;
	}
	return ans;
}
void dfs(int x)
{
	
	
	//book[x] = 1;
	for(int i = 0;i < v[x].size();i++)
	{
		if(v[x][i].to == father[x].to)
			continue;
		int t = v[x][i].to;
		//Union(x,t);
		//if(book[t] == 0)
			dfs(t);
		Union(x,t);
		book[t] = 1;
	}
	
	
	for(int j = 0;j < question[x].size();j++)
	{
		if(book[question[x][j].to] == 1)
		{
			ans[question[x][j].dis] = LCA(x,question[x][j].to);
			
		
			//cout << LCA(x)+LCA(question[x][j]) << endl;
		}
	}
	return;
}


int main()
{
	int i,j,k;
	freopen("distance.in","r",stdin);
	freopen("distance.out","w",stdout);
	cin >> n >> m;
	for(i = 1;i < n;i++)
	{
		b[i] = i;
		int u1,v1,w;
		cin>>u1>>v1>>w;
		N U,V;
		U.to=v1;
		U.dis=w;
		V.to=u1;
		V.dis=w;
	
		v[u1].push_back(U);
		v[v1].push_back(V);
		
	}
	b[n] = n;
	build(1);
	for(i = 1;i <= m;i++)
	{
		int t1,t2;
		//cin >> q1[i] >> q2[i];
		cin >> t1 >> t2;
		A.to = t2;
		A.dis = i;
		B.to = t1;
		B.dis = i;
		question[t1].push_back(A);
		question[t2].push_back(B);
	}
	dfs(1);
	for(i = 1;i <= m;i++)
	{
		cout << ans[i] << endl;
	}
	return 0;
}