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

#include<stdio.h>
#include<iostream>
#include<algorithm>
#define maxn 100050
#define inf 1e+9
using namespace std;
int n,m,q;
struct edge{
	int ne;
	int from,to,v;
}e[maxn*2];
int tot;
int f[maxn];
int son[maxn];
int data[maxn];
int top[maxn];
int head[maxn];
int deep[maxn];
int size[maxn];
int intree[maxn];
int outree[maxn];
void dfs1(int now,int de,int fa){
	deep[now]=de;f[now]=fa;size[now]=1;
	for(int i=head[now];i;i=e[i].ne){
		int tmp=e[i].to;
		if(tmp==fa)continue;
		data[tmp]=e[i].v;
		dfs1(tmp,de+1,now);
		size[now]+=size[tmp];
		if(!son[now]||size[tmp]>size[son[now]]){
			son[now]=tmp;
		}
	}
}
void dfs2(int now,int t){
	top[now]=t;intree[now]=++tot;
	outree[tot]=now;
	if(son[now]){
		dfs2(son[now],t);
	}else{
		return;
	}
	for(int i=head[now];i;i=e[i].ne){
		int tmp=e[i].to;
		if(tmp!=son[now]&&tmp!=f[now]){
			dfs2(tmp,tmp);
		}
	}
}
class SegTree{
private:
	struct node{
		int l,r;
		int sum;
	}ns[maxn*4];
public:
	void build_tree(int l,int r,int i){
		ns[i].l=l;
		ns[i].r=r;
		ns[i].sum=data[outree[l]];
		if(l==r){
			return;
		}
		build_tree(l,(l+r)/2,i*2);
		build_tree((l+r)/2+1,r,i*2+1);
		ns[i].sum=ns[i*2].sum+ns[i*2+1].sum;
	}
	int querysum(int l,int r,int i){
		if(ns[i].l==l&&ns[i].r==r){
			return ns[i].sum;
		}else if(r<=ns[i*2].r){
			return querysum(l,r,i*2);
		}else if(l>=ns[i*2+1].l){
			return querysum(l,r,i*2+1);
		}else{
			return querysum(l,ns[i*2].r,i*2)+querysum(ns[i*2+1].l,r,i*2+1);
		}
	}
}ST;
int querysum(int from,int to){
	int f1=top[from],f2=top[to],ans=0;
	while(f1!=f2){
		if(deep[f1]<deep[f2]){
			f1+=f2;f2=f1-f2;f1-=f2;
			from+=to;to=from-to;from-=to; 
		}
		ans+=ST.querysum(intree[f1],intree[from],1);
		from=f[f1];f1=top[from];
	}
	ans+=((deep[from]>deep[to])?
		(ST.querysum(intree[to],intree[from],1)-ST.querysum(intree[to],intree[to],1)):
		(ST.querysum(intree[from],intree[to],1)-ST.querysum(intree[from],intree[from],1)));
	return ans;
}
void solve(){
	dfs1(1,1,1);
	dfs2(1,1);
	ST.build_tree(1,n,1);
	scanf("%d",&q);
	for(int i=1;i<=q;++i){
		int fr,to;
		scanf("%d %d",&fr,&to);
		printf("%d\n",querysum(fr,to));
	}
}
void read(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;++i){
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		e[i].from=a;e[i].to=b;e[i].v=c;
		e[i].ne=head[a];
		head[a]=i;
		e[i+n].from=b;e[i+n].to=a;e[i+n].v=c;
		e[i+n].ne=head[b];
		head[b]=i+n;
	}
}
int main(){
	freopen("ThefallingofZLX.in","r",stdin);
	freopen("ThefallingofZLX.out","w",stdout);
	read();
	solve();
	return 0;
}