记录编号	323167	评测结果	AAAAAAAAAA
题目名称	[ZLXOI 2015][异次元圣战III]ZLX的陨落	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	0.326 s
提交时间	2016-10-16 06:15:20	内存使用	17.08 MiB

#include<cstdio>
const int maxn = 100010 << 2 ;
int top[maxn],son[maxn],size[maxn],deep[maxn],dfn[maxn],dis[maxn],fa[maxn];
int cnt,tot,head[maxn],n,m,q,x,y,z;
struct Edge{
	int to,next,dis;
}edge[maxn];
void Addedge(int x,int y,int z){
	edge[++tot].to=y;
	edge[tot].next=head[x];
	edge[tot].dis=z;
	head[x]=tot;
}
void dfs1(int x){
	size[x]=1;
	for(int i=head[x];i;i=edge[i].next){
		int p = edge[i].to;
		if(!size[p]){
			deep[p] = deep[x] + 1;
			fa[p]=x;
			dis[p] = dis[x] + edge[i].dis;
			dfs1(p);
			size[x] += size[p];
			if(size[p]>size[son[x]])son[x]=p;
		}
	}
}
void dfs2(int x,int tp){
	top[x]=tp;dfn[x]=++cnt;
	if(son[x])dfs2(son[x],tp);
	for(int i=head[x];i;i=edge[i].next){
		int p=edge[i].to;
		if(!dfn[p])dfs2(p,p);
	}
}
/*************************就是这两个LCA！QAQ*************************/
int lca(int x,int y){
	while(top[x]!=top[y]){
		if(size[top[x]]>size[top[y]])x^=y^=x^=y;
		x=fa[top[x]];
	}
	if(deep[x]>deep[y])return y;
	else return x;
}
int two_lca(int x,int y){
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]])x^=y^=x^=y;
		x=fa[top[x]];
	}
	if(deep[x]>deep[y])return y;
	else return x;
}
/********************************************************************/
int main(){
	freopen("ThefallingofZLX.in","r",stdin);
	freopen("ThefallingofZLX.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		Addedge(x,y,z);
		Addedge(y,x,z);
    }
    deep[1]=1;
    dfs1(1),dfs2(1,1);
    scanf("%d",&q);
    while(q--){
		scanf("%d%d",&x,&y);
		int d = dis[x] + dis[y] - 2 * dis[two_lca(x,y)];
		printf("%d\n",d);
	}
}