记录编号	302008	评测结果	AAAAAAAAAA
题目名称	距离	最终得分	100
用户昵称	ミント	是否通过	通过
代码语言	C++	运行时间	1.405 s
提交时间	2016-09-03 09:06:46	内存使用	1.47 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

#include <vector>
#include <queue>

using namespace std;

const int maxn = 10000 + 100;
vector<int> G[maxn], C[maxn];
int p[maxn][21+5], f[maxn], level[maxn];
bool l[maxn];
int n, m;

void Init(){
	memset(l, false, sizeof(l));
	memset(f, 0, sizeof(f));
	memset(p, 0, sizeof(p));
	memset(level, 0, sizeof(level));
	return ;
}
void BFS(int start){
	bool vis[maxn];memset(vis, false, sizeof(vis));
	queue<int> q;
	
	q.push(start);
	while(!q.empty()){
		int u = q.front();q.pop();
		vis[u] = true;
		for(int i=0;i<G[u].size();i++){
			int v = G[u][i], w = C[u][i];
			if(!vis[v]){
				p[v][0] = u;
				level[v] = level[u] + 1;
				f[v] = f[u] + w;
				q.push(v);
			}
		}
	}
	return ;
}
inline void LCB(int u){
	l[u] = true;
	for(int i=1;i<21;i++){
		p[u][i] = p[p[u][i-1]][i-1];
		if(!p[u][i])break;
	}
	for(int i=0;i<G[u].size();i++){
		int v = G[u][i];
		if(!l[v])LCB(v);
	}
	return ;
}
inline int LCA(int u, int v){
	if(level[u]<level[v])swap(u, v);
	int dif = level[u] - level[v];
	for(int i=0;i<21;i++)
		if((1<<i)&dif)
			u = p[u][i];
	if(u==v)return u;
	for(int i=21-1;i>=0;i--)
		if(p[u][i]!=p[v][i]){
			u = p[u][i];
			v = p[v][i];
		}
	u = p[u][0];
	return u;
}
inline int dis(int u, int v){
	int fa = LCA(u, v);
	int ret = f[u] +  f[v] - f[fa] * 2;
	return ret;
}
int main(){
	freopen("distance.in", "r", stdin);
	freopen("distance.out", "w", stdout);
	
	Init();
	cin>>n>>m;
	for(int i=1;i<=n-1;i++){
		int u, v, w;cin>>u>>v>>w;
		G[u].push_back(v);G[v].push_back(u);
		C[u].push_back(w);C[v].push_back(w);
	}
	BFS(1);LCB(1);
	while(m--){
		int a, b;cin>>a>>b;
		cout<<dis(a, b)<<endl;
	}
	return 0;
}