记录编号	309712	评测结果	AAAAAAAAAA
题目名称	[USACO Feb04]距离咨询	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.183 s
提交时间	2016-09-20 15:21:20	内存使用	6.19 MiB

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 4e4 + 10;
const int bit_top = 16;


struct Edge {
	int to, ne, v;
	Edge() {}
	Edge(int to_, int ne_, int v_) { to = to_, ne = ne_, v = v_; }
} e[maxn << 1];
int head[maxn], ecnt;
inline void add_edge(int fr, int to, int v) {
	e[++ecnt] = Edge(to, head[fr], v), head[fr] = ecnt;
	e[++ecnt] = Edge(fr, head[to], v), head[to] = ecnt;
}


int n, m;
int mul_fa[maxn][17], mul_dis[maxn][17];
int deep[maxn];
int r_dis[maxn];


#define is_num(x) (x <= '9' and x >= '0')
inline int get_num() {
	char tmp = getchar();
	int res = 0;
	
	while (not is_num(tmp)) tmp = getchar();
	while (    is_num(tmp)) {
		res = (res << 3) + (res << 1) + tmp - '0';
		tmp = getchar();
	}
	
	return res;
}


inline void read() {
	n = get_num(), m = get_num();
	for (int i = 1; i <= m; i++) {
		int fr = get_num(), to = get_num(), v = get_num();
		add_edge(fr, to, v);
	}
}


void get_info(int now) {
	for (int i = 1; i <= bit_top; i++) {
		if (deep[now] < 1 << i) break;
		
		int la_fa = mul_fa[now][i - 1];
		mul_fa[now][i] = mul_fa[la_fa][i - 1];
		mul_dis[now][i] = mul_dis[la_fa][i - 1] + mul_dis[now][i - 1];
	}
	
	for (int i = head[now]; i; i = e[i].ne) {
		int to = e[i].to;
		if(deep[to]) continue;
		
		deep[to] = deep[now] + 1;
		mul_fa[to][0] = now;
		mul_dis[to][0] = e[i].v;
		r_dis[to] = r_dis[now] + e[i].v;
		
		get_info(to);
	}
}


int cal(int u, int v) {
	if (deep[u] < deep[v]) swap(u, v);
	int delta = deep[u] - deep[v], dis = 0;
	
	for (int i = bit_top; i >= 0; i--) if (delta & (1 << i)) dis += mul_dis[u][i], u = mul_fa[u][i];
	
	for (int i = bit_top; i >= 0; i--) {
		if (mul_fa[u][i] == mul_fa[v][i]) continue;
		
		dis += mul_dis[u][i] + mul_dis[v][i];
		u = mul_fa[u][i], v = mul_fa[v][i];
	}
	
	if (u == v) return dis;
	return dis + mul_dis[u][0] + mul_dis[v][0];
}


int get_lca(int u, int v) {
	if(deep[u] < deep[v]) swap(u, v);
	
	int delta = deep[u] - deep[v];
	for(int i = 0; i <= bit_top; i++) if(delta & (1 << i)) u = mul_fa[u][i];
	
	for(int i = bit_top; i >= 0; i--) if(mul_fa[u][i] != mul_fa[v][i]) u = mul_fa[u][i], v = mul_fa[v][i];
	
	if(u == v) return u;
	return mul_fa[u][0];
}


inline void solve() {
	deep[1] = 1;
	get_info(1);
	
	int t = get_num();
	for (int i = 1; i <= t; i++) {
		int fr = get_num(), to = get_num();
		// printf("%d\n", r_dis[fr] + r_dis[to] - (r_dis[get_lca(fr, to)] << 1));
		printf("%d\n", cal(fr, to));
	}
}


int main() {
	freopen("dquery.in", "r", stdin);
	freopen("dquery.out", "w", stdout);
	read();
	solve();
	return 0;
}