记录编号	304548	评测结果	AAAAAAAAAA
题目名称	[ZLXOI 2015][异次元圣战III]ZLX的陨落	最终得分	100
用户昵称	iortheir	是否通过	通过
代码语言	C++	运行时间	1.899 s
提交时间	2016-09-08 16:43:12	内存使用	10.59 MiB

#include<iostream>
#include<cstdio>
#include<vector>

using namespace std;

const int maxn=100000+100;
const int maxm=200000+100;

int n;
int m;

int q;

int a;
int b;
int w;
int kount1=1;
int kount2=1;
int head[maxn];
int head1[maxn];
int father[maxn];
int rank[maxn];
int u[maxm];
int v[maxm];

int vis[maxn];
int dis[maxn];

int lca[maxm];

struct T1
{
	int to;
	int next;
	int w;
}A1[2*maxn];

inline void adde(int a,int b,int w)
{
	A1[++kount1].next=head[a];
	A1[kount1].to=b;
	A1[kount1].w=w;
	head[a]=kount1;
}

struct T2
{
	int to;
	int next;
	int w;
}A2[2*maxm];

inline void addq(int a,int b,int w)
{
	A2[++kount2].next=head1[a];
	A2[kount2].to=b;
	A2[kount2].w=w;
	head1[a]=kount2;
}

inline int find(int x)
{
	if(father[x]!=x)
	{
		father[x]=find(father[x]);
	}
	return father[x];
}

inline void unionn(int x,int y)
{
	father[x]=y;
}

inline void tarjan(int x)
{
	vis[x]=1;
	for(int i=head[x];i;i=A1[i].next)
	{
		if(!vis[A1[i].to])
		{
			dis[A1[i].to]=dis[x]+A1[i].w;
			tarjan(A1[i].to);
			unionn(A1[i].to,x);
		}
	}
	vis[x]=2;
	for(int i=head1[x];i;i=A2[i].next)
	{
		if(vis[A2[i].to]==2)
		{
			lca[A2[i].w]=find(A2[i].to);
		}
	}
}

int main()
{
	freopen("ThefallingofZLX.in","r",stdin);
	freopen("ThefallingofZLX.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		father[i]=i;
	}
	for(int i=1;i<n;++i)
	{
		scanf("%d%d%d",&a,&b,&w);
		adde(a,b,w);
		adde(b,a,w);
	}
	scanf("%d",&q);
	for(int i=1;i<=q;++i)
	{
		scanf("%d%d",&u[i],&v[i]);
		addq(u[i],v[i],i);
		addq(v[i],u[i],i);
	}
	tarjan(1);
	for(int i=1;i<=q;++i)
	{
		cout<<dis[v[i]]+dis[u[i]]-dis[lca[i]]*2<<endl;
	}
	return 0;
}