记录编号	269650	评测结果	AAAAAAAAAA
题目名称	[USACO Feb04]距离咨询	最终得分	100
用户昵称	哒哒哒哒哒！	是否通过	通过
代码语言	C++	运行时间	0.052 s
提交时间	2016-06-13 20:18:34	内存使用	17.10 MiB

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>

using namespace std;
const int maxn=400001;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-48;
		ch=getchar();
	}
	return x*f;
}
struct edge{
	int to,next,dis;
}e[maxn];
int tot,head[maxn];
void add(int u,int v,int w){
	e[++tot].to=v;
	e[tot].dis=w;
	e[tot].next=head[u];
	head[u]=tot;
}
int size[maxn],fa[maxn],son[maxn],deep[maxn],dis[maxn],top[maxn],dfs_clock,dfn[maxn];
void dfs(int u){
	size[u]=1;
	for(int i=head[u];i;i=e[i].next){
		int to=e[i].to;
		if(size[to]) continue;
		fa[to]=u;
		deep[to]=deep[u]+1;
		dis[to]=dis[u]+e[i].dis;
		dfs(to);
		size[u]+=size[to];
		if(size[son[u]]<size[to]) son[u]=to;
	}
}

void rebuild(int u,int tp){
	top[u]=tp;
	dfn[u]=++dfs_clock;
	if(son[u]) rebuild(son[u],tp);
	for(int i=head[u];i;i=e[i].next){
		int to=e[i].to;
		if(!dfn[to]) rebuild(to,to);
	}
}

int LCA(int a,int b){
	while(top[a]!=top[b]){
		if(deep[top[a]]<deep[top[b]]) swap(a,b);
		a=fa[top[a]];
	}
	return deep[a]>deep[b] ? b :a;
}

void Build(){
	deep[1]=1;
	dfs(1);
	rebuild(1,1);
}
int main(){
	freopen("dquery.in","r",stdin);freopen("dquery.out","w",stdout);
	int n=read(),m=read();
	for(int i=1;i<=m;i++){
		int a=read(),b=read(),w=read();getchar();
		add(a,b,w);
		add(b,a,w);
	}
	Build();
	int q=read();
	while(q--){
		int a=read(),b=read();
		printf("%d\n",dis[a]+dis[b]-(dis[LCA(a,b)]*2));
	}
	fclose(stdin);fclose(stdout);
	return 0;
}