记录编号	206166	评测结果	AAAAAAAAAA
题目名称	[ZLXOI 2015][异次元圣战III]ZLX的陨落	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	1.678 s
提交时间	2015-11-06 09:08:03	内存使用	21.85 MiB

#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<ctime>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=300000+10;
int n,m,h[maxn],q,tot=0;
LL dis[maxn];
struct edge{
	int to,next,w;
}G[maxn];
int p[maxn][20];
int deep[maxn];
char ch;

int read(){
	int num=0; ch=getchar();
	while (ch<'!') ch=getchar();
	while (ch>='0'&&ch<='9'){num=num*10+ch-'0';ch=getchar();}
	return num;
}

void add(int x,int y,int z){
	++tot; G[tot].w=z; G[tot].to=y;
	G[tot].next=h[x]; h[x]=tot;
}

int LCA(int a,int b){
	if (deep[a]<deep[b]) swap(a,b);
	for (int j=19;~j;j--)
	   if (deep[p[a][j]]>=deep[b])
		  a=p[a][j];
	if (a==b) return a;
	for (int j=19;~j;--j)
	   if (p[a][j]!=-1&&p[a][j]!=p[b][j]){
			a=p[a][j]; b=p[b][j];
	   }
	return p[a][0];
}

void ask(int x,int y){
	int zx=LCA(x,y);
	if (zx==-1) zx=0;
	printf("%lld\n",dis[x]+dis[y]-2*dis[zx]);
}

void DFS(int x,int fa,int dist,int dep){
	dis[x]=dist; deep[x]=dep;
	for (int i=h[x];i;i=G[i].next){
		if (G[i].to==fa) continue;
		p[G[i].to][0]=x;
		DFS(G[i].to,x,dist+G[i].w,dep+1);
	}
}

int main(){
	freopen("ThefallingofZLX.in","r",stdin);
	freopen("ThefallingofZLX.out","w",stdout);
	memset(p,-1,sizeof(p));
	n=read(); m=read();
	for (int i=1;i<=m;++i){
		int x=read(),y=read(),z=read();
		add(x,y,z); add(y,x,z);
	}
	DFS(1,-1,0,0);
	for (int j=1;j<=19;++j)
	   for (int i=1;i<=n;++i)
		   if (p[i][j-1]!=-1)
			  p[i][j]=p[p[i][j-1]][j-1];
	scanf("%d",&q);
	for (int i=1;i<=q;++i){
		int x=read(),y=read();
		ask(x,y);
	}
	return 0;
}