记录编号	536816	评测结果	AAAAAAAAAA
题目名称	距离	最终得分	100
用户昵称	Deacep	是否通过	通过
代码语言	C++	运行时间	0.822 s
提交时间	2019-07-08 17:14:59	内存使用	14.51 MiB

//LCA_Tarjan
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct qwq{
	int e,w;
	qwq(int x,int y):e(x),w(y){}
};
vector<qwq> fir[10004];
int f[10004];
int dis[10004];
int ans[20004];
bool vis[10004];
//int head,tail;
struct que{
	int ad;
	int num;
	que(int x,int y):ad(x),num(y){}
};
vector<que> q[20004];
int _find(int x){
	if(x!=f[x])
	return f[x]=_find(f[x]);
	return x;
}
void Init(){
	memset(dis,0,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(f,0,sizeof(f));
}
void _union(int x,int y){
	if(_find(x)!=_find(y))f[f[y]]=f[x];//就是这样写没错，注意看42行 
}
void dfs(int pre,int pr,int d){
	f[pr]=pr;
	dis[pr]=d;
	for(int i=0;i<fir[pr].size();i++){
		if(fir[pr][i].e!=pre){//条件1无影响 //(!vis[fir[pr][i].e])&&
			dfs(pr,fir[pr][i].e,d+fir[pr][i].w);
//		int nx=fir[pr][i].e;
//		cout<<pr<<' '<<f[pr]<<' '<<nx<<' '<<f[nx]<<"->";
		_union(pr,fir[pr][i].e);}//如果括号不包括这里，相当于儿子认爸爸做儿子，有悖伦理(然而并查集岂不是。。。 
//		cout<<f[f[pr]]<<' '<<f[f[nx]]<<endl;
	}
	vis[pr]=1;
	for(int i=0;i<q[pr].size();i++){
		if(vis[q[pr][i].ad]){
//		cout<<pr<<' '<<dis[pr]<<' '<<q[pr][i].ad<<' '<<dis[q[pr][i].ad]<<' '<<_find(q[pr][i].ad)<<' '<<dis[_find(q[pr][i].ad)]<<endl;
		ans[q[pr][i].num]=dis[pr]+dis[q[pr][i].ad]-2*dis[_find(q[pr][i].ad)];
		}
	}
}
void print(){
	for(int i=0;i<m;i++)
	cout<<ans[i]<<endl;
}
int main(){
	Init();
	freopen("distance.in","r",stdin);
	freopen("distance.out","w",stdout);
	cin>>n>>m;
	int _p,_q,r;
	for(int i=0;i<n-1;i++){
		cin>>_p>>_q>>r;
		fir[_p].push_back(qwq(_q,r));
		fir[_q].push_back(qwq(_p,r));
	}
	for(int i=0;i<m;i++){
		cin>>_p>>_q;
		q[_p].push_back(que(_q,i));
		q[_q].push_back(que(_p,i));
	}
	dfs(0,1,0);
	print();
	return 0;
}