记录编号	301963	评测结果	AAAAAAAAAA
题目名称	距离	最终得分	100
用户昵称	农场主	是否通过	通过
代码语言	C++	运行时间	0.999 s
提交时间	2016-09-03 08:26:07	内存使用	70.88 MiB

#include<cstdio>
#include<vector>
#include<algorithm>
#define maxn 2000000
using namespace std;
int n,m;
vector<int> G[maxn],Q[maxn];
int d[maxn]={0},t[maxn]={0};
int f[maxn]={0};
void init(int n){
	for (int i=1;i<=n;i++){
		f[i]=i;
	}
}
int find(int x){
	return x==f[x]?x:f[x]=find(f[x]);
}
void merge(int a,int b){
	f[find(a)]=find(b);
}
struct poi{
	int from,to,ans; 
};
vector<poi> q;
vector<poi> edges;
bool vis[maxn]={0};
#define e edges[G[x][i]]
void dfs(int x){
	vis[x]=1;
	//t[x]+=d[x];
	for (int i=0;i<G[x].size();i++)if ((vis[e.from]&vis[e.to])==0){
		int to;
		if (vis[e.from]==1) to=e.to;
		else to=e.from;
		t[to]=e.ans+t[x];
		//printf("		%d %d\n",to,t[to]);
		dfs(to);
		merge(to,x);
	}
	for (int i=0;i<Q[x].size();i++){
		poi &p=q[Q[x][i]];
		if (vis[p.from]&vis[p.to]==1){
			if (p.from==x){
				p.ans=find(p.to);
			}
			else{
				p.ans=find(p.from);
			}
		}
	}
}
void read(){
	scanf("%d",&n);
	scanf("%d",&m);
	init(n);
	/*for (int i=1;i<=n;i++){
		scanf("%d",&d[i]);
	}*/ 
	for (int i=1;i<n;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w); 
		edges.push_back((poi){u,v,w});
		G[u].push_back(edges.size()-1);
		G[v].push_back(edges.size()-1);
	}
	for (int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d",&u,&v);
		q.push_back((poi){u,v,0});
		Q[u].push_back(q.size()-1);
		Q[v].push_back(q.size()-1);
	}
	dfs(1);
	//printf("	%d %d %d\n",t[3],t[2],t[1]);
	for (int i=0;i<m;i++){
		printf("%d\n",t[q[i].from]+t[q[i].to]+d[q[i].ans]-t[q[i].ans]*2);
	}
}
int main(){
	freopen("distance.in","r",stdin);
	freopen("distance.out","w",stdout);
	read();
	return 0;
}