记录编号	212745	评测结果	AAAAAAAAAA
题目名称	[ZLXOI 2015][异次元圣战III]ZLX的陨落	最终得分	100
用户昵称	lyxin65	是否通过	通过
代码语言	C++	运行时间	0.459 s
提交时间	2015-12-07 20:27:24	内存使用	12.52 MiB

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;
const int maxm = 200005;
const int maxlog = 20;

int n, m, logn;
int head[maxn];
int next[maxm];
int u[maxm], v[maxm], w[maxm];

void init_graph()
{
	logn = m = 0;
	while((1 << logn) < n) ++logn;
	memset(head, -1, sizeof(head));
}

inline void addedge(int a, int b, int c)
{
	u[m] = a, v[m] = b, w[m] = c; next[m] = head[a], head[a] = m++;
	u[m] = b, v[m] = a, w[m] = c; next[m] = head[b], head[b] = m++;
}

void input()
{
	scanf("%d%*d", &n);
	init_graph();
	for(int i = 1; i < n; ++i)
	{
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		addedge(x, y, z);
	}
}


int depth[maxn];
long long dis[maxn];
int fa[maxn][maxlog];

void dfs(int x, int p)
{
	fa[x][0] = p;
	for(int i = 1; i <= logn; ++i)
		if(!(fa[x][i] = fa[fa[x][i-1]][i-1]))
			break;
	for(int i = head[x]; ~i; i = next[i])
	{
		if(v[i] != p)
		{
			int k = v[i];
			depth[k] = depth[x] + 1;
			dis[k] = dis[x] + w[i];
			dfs(k, x);
		}
	}
}

void build()
{
	dfs(1, 0);
}

int lca(int a, int b)
{
	if(depth[a] < depth[b]) swap(a, b);
	for(int i = logn; i >= 0; --i)
		if(depth[fa[a][i]] >= depth[b])
			a = fa[a][i];
	if(a == b) return a;
	for(int i = logn; i >= 0; --i)
		if(fa[a][i] != fa[b][i])
			a = fa[a][i], b = fa[b][i];
	return fa[a][0];
}

void solve()
{
	int Q;
	scanf("%d", &Q);
	while(Q--)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		printf("%lld\n", dis[a] + dis[b] - 2 * dis[lca(a, b)]);
	}
}

int main()
{
	freopen("ThefallingofZLX.in", "r", stdin);
	freopen("ThefallingofZLX.out", "w", stdout);
	
	input();
	build();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}