记录编号	397813	评测结果	AAAAAAAAAA
题目名称	距离	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	0.057 s
提交时间	2017-04-20 21:43:15	内存使用	1.51 MiB

#include<cstdio>
using namespace std;
const int maxn=10000+10;
const int M=20005;
int n,m;
int ance[maxn],f[maxn],vis[maxn],dis[maxn],lca[M],u[M],v[M];
int to[maxn*2],first[maxn],qfirst[M],next[maxn*2],qnext[M*2],qto[M*2],w[maxn*2],qss[M*2];
void init(int n){
	for(int i=1;i<=n;i++){
		f[i]=i;
		vis[i]=0;
		ance[i]=i;
		qfirst[i]=first[i]=-1;
	}
}
void dfs(int x,int fa,int dist){
	dis[x]=dist;
	for(int i=first[x];i!=-1;i=next[i]){
		if(to[i]!=fa)
			dfs(to[i],x,dist+w[i]);
	}
}
int find(int n){
	if(f[n]==n)return n;
	else return f[n]=find(f[n]);
}
void Union(int x,int y){
	int a=find(x);
	int b=find(y);
	if(a!=b)f[a]=b;
}
void LCA(int u,int fa){
	for(int i=first[u];i!=-1;i=next[i]){
		if(to[i]!=fa){
			LCA(to[i],u);
			Union(to[i],u);
			ance[find(u)]=u;
		}
	}
	vis[u]=1;
	for(int i=qfirst[u];i!=-1;i=qnext[i]){
		if(vis[qto[i]]){
			lca[qss[i]]=ance[find(qto[i])];
		}
	}
}

int work(){
	freopen("distance.in","r",stdin);
	freopen("distance.out","w",stdout);
	scanf("%d%d",&n,&m);
	init(n);
	int a,b,c,num=0;
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&a,&b,&c);
		to[++num]=b,next[num]=first[a],first[a]=num,w[num]=c,
		to[++num]=a,next[num]=first[b],first[b]=num,w[num]=c;
	}
	dfs(1,1,0);
	num=0;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u[i],&v[i]);
		qto[++num]=v[i],qnext[num]=qfirst[u[i]],qfirst[u[i]]=num,qss[num]=i,
		qto[++num]=u[i],qnext[num]=qfirst[v[i]],qfirst[v[i]]=num,qss[num]=i;
	}
	LCA(1,1);
	for(int i=1;i<=m;i++)printf("%d\n",dis[u[i]]+dis[v[i]]-dis[lca[i]]*2);
	return 0;
}
int sh=work();
int main(){
	return 0;
}