记录编号	448992	评测结果	AAAAAAAAAA
题目名称	距离	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.175 s
提交时间	2017-09-13 17:24:47	内存使用	1.35 MiB

#include<bits/stdc++.h>//tarjan,感觉我写的好奇怪啊..好多地方都不太会处理用了很奇怪的方法 
#define v e[i].to
using namespace std;
const int ma=10005;
int n,m,fi[ma],tot,fa[ma],vis[ma],dis[ma];
struct edge{
	int to,next,cost;
}e[ma<<1];
void edge_add(int x,int y,int z){
	e[++tot].to=y;
	e[tot].next=fi[x];
	fi[x]=tot;
	e[tot].cost=z;
}
struct path{
	int s,t,lc;
}p[ma<<1];//这里开询问次数大小..不要开错了 
struct ha{
	int to,num;
}s[ma<<2];
vector<int>a[ma];
int get_fa(int x){
	return x==fa[x]?x:fa[x]=get_fa(fa[x]);
}
void dfs(int x,int f){
	for(int i=fi[x];i;i=e[i].next){
		if(v==f)continue;
		dis[v]=dis[x]+e[i].cost;
		dfs(v,x);
	}
	int si=a[x].size();
	vis[x]=1;//写在前面，有可能查询自己和自己的lca 
	for(int i=0;i<si;i++){ 
		ha &o=s[a[x][i]];
		if(!vis[o.to])continue;
		p[o.num].lc=get_fa(o.to);
	}
	fa[x]=f;//这句得写到查找的后面，不然当他查询他和他儿子的lca就查到他的父亲了 
}
int main()
{
	freopen("distance.in","r",stdin);
	freopen("distance.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		edge_add(x,y,z);
		edge_add(y,x,z);
	}
	for(int i=1;i<=n;i++)fa[i]=i;
	tot=0;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&p[i].s,&p[i].t);
		s[++tot].to=p[i].s;s[tot].num=i;
		a[p[i].t].push_back(tot);
		s[++tot].to=p[i].t;s[tot].num=i;
		a[p[i].s].push_back(tot);
	}
	dfs(1,1);
	for(int i=1;i<=m;i++){
		printf("%d\n",dis[p[i].s]+dis[p[i].t]-(dis[p[i].lc]<<1));
	}
	return 0;
}