记录编号	438182	评测结果	AAAAAAAAAA
题目名称	[ZLXOI 2015][异次元圣战III]ZLX的陨落	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	0.461 s
提交时间	2017-08-15 16:23:23	内存使用	8.71 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
const int M=100000+10;
int n,m,num,cnt,q;
int head[2*M],dep[M],size[M],son[M],fa[M],v[M];
int top[M],pos[M],id[M];
int sum[4*M];
struct DATE{int fr,to,w,last;}date[2*M];
inline 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-'0';ch=getchar();}
    return x*f;
}
inline void add(int x,int y,int z){
	date[++num]=(DATE){x,y,z,head[x]};
	head[x]=num;
}
void dfs1(int x){
	size[x]=1;
	for(int i=head[x];i;i=date[i].last){
		int to=date[i].to,w=date[i].w;
		if(to!=fa[x]){
			fa[to]=x;dep[to]=dep[x]+1;v[to]=w;
			dfs1(to);size[x]+=size[to];
			if(size[son[x]]<size[to]) son[x]=to;
		}
	}
}
void dfs2(int x,int tp){
	top[x]=tp;id[x]=++cnt;pos[cnt]=x;
	if(son[x]) dfs2(son[x],tp);
	for(int i=head[x];i;i=date[i].last){
		int to=date[i].to;
		if(to!=fa[x]&&to!=son[x])
			dfs2(to,to);
	}
}
void bt(int rt,int l,int r){
	if(l==r) {sum[rt]=v[pos[l]];return ;}
	int mid=l+r>>1;
	bt(lson);bt(rson);
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
int query(int s,int t,int rt,int l,int r){
	if(s<=l&&r<=t) return sum[rt];
	int mid=l+r>>1; int res=0;
	if(s<=mid) res+=query(s,t,lson);
	if(t>mid) res+=query(s,t,rson);
	return res;
}
int Query(int x,int y){
	int fx=top[x],fy=top[y];int res=0;
	while(fx!=fy){
		if(dep[fx]<dep[fy])
			swap(x,y),swap(fx,fy);
		res+=query(id[fx],id[x],1,1,n);
		x=fa[fx];fx=top[x];
	}
	if(dep[x]>dep[y]) swap(x,y);
	res+=query(id[x]+1,id[y],1,1,n);
	return res;
}
int main(){
	freopen("ThefallingofZLX.in","r",stdin);
	freopen("ThefallingofZLX.out","w",stdout);
	n=read();m=read();int aa,bb,cc;
	for(int i=1;i<=m;i++){
		aa=read();bb=read();cc=read();
		add(aa,bb,cc);add(bb,aa,cc);
	}
	dfs1(1);dfs2(1,1);bt(1,1,n);q=read();
	for(int i=1;i<=q;i++){
		aa=read();bb=read();
		printf("%d\n",Query(aa,bb));
	}
	return 0;
}