记录编号	301930	评测结果	AAAAAAAAAA
题目名称	距离	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.317 s
提交时间	2016-09-02 22:54:36	内存使用	0.73 MiB

//KZNS
#include <cstdio>
#include <vector>
#include <utility>
using namespace std;
#define Nmax 10003
#define Mmax 20003
typedef pair<int, int> pr;

int N, M;
vector<pr> gp[Nmax];
vector<pr> qls[Nmax];
int ans[Mmax] = {0};
void rin() {
	scanf("%d %d", &N, &M);
	int a, b, c;
	for (int i = 1; i < N; i++) {
		scanf("%d %d %d", &a, &b, &c);
		gp[a].push_back(make_pair(b, c));
		gp[b].push_back(make_pair(a, c));
	}
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &a, &b);
		qls[a].push_back(make_pair(b, i));
		qls[b].push_back(make_pair(a, i));
	}
}
int fa[Nmax] = {0};
int v[Nmax] = {0};
int FA(int x) {
	if (fa[x] != x) {
		int t = fa[x];
		fa[x] = FA(fa[x]);
		v[x] += v[t];
	}
	return fa[x];
}
bool ud[Nmax] = {false};
vector<pair<pr, int> > als[Nmax];
void DFS(int x) {
	ud[x] = true;
	fa[x] = x;
	int t;
	for (int i = 0; i < gp[x].size(); i++) {
		t = gp[x][i].first;
		if (!ud[t]) {
			DFS(t);
			fa[t] = x;
			v[t] = gp[x][i].second;
		}
	}
	for (int i = 0; i < qls[x].size(); i++) {
		t = qls[x][i].first;
		if (fa[t])
			als[FA(t)].push_back(make_pair(make_pair(x, t), qls[x][i].second));
	}
	for (int i = 0; i < als[x].size(); i++) {
		t = FA(als[x][i].first.first);
		ans[als[x][i].second] = v[als[x][i].first.first] + v[als[x][i].first.second];
	}
}
void pot() {
	for (int i = 0; i < M; i++)
		printf("%d\n", ans[i]);
}
int main() {
	freopen("distance.in", "r", stdin);
	freopen("distance.out", "w", stdout);
	rin();
	DFS(1);
	pot();
	return 0;
}
//UWBH