记录编号	234283	评测结果	AAAAAAAAAA
题目名称	[ZLXOI 2015][异次元圣战III]ZLX的陨落	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	1.466 s
提交时间	2016-03-07 18:21:51	内存使用	20.15 MiB

//KZNS
#include <fstream>
#include <utility>
#include <vector>
using namespace std;
//
ifstream fin ("ThefallingofZLX.in");
ofstream fout ("ThefallingofZLX.out");
typedef pair<int, int> poi;
//
int n, m, q;
vector<poi> mp[100002];
int rmq[200002][22];
int fap[100002]={0};
int dlist[200002];
int ddp[100002];
int dlth[100002];
int tim=1;
//
inline int mn(int a, int b) {
	if (ddp[b]<ddp[a])
		return b;
	return a;
}
inline int loog(int k) {
	for (int u=1,i=0; true; i++)
		if (k<(u<<=1))
			return i;
}
void DFS(int x, int dp, int lth) {
	ddp[x]=dp;
	dlth[x]=lth;
	fap[x]=tim;
	dlist[tim++]=x;
	for (int i=0; i<mp[x].size(); i++) {
		if (!fap[mp[x][i].first]) {
			DFS(mp[x][i].first, dp+1, lth+mp[x][i].second);
			dlist[tim++]=x;
		}
	}
}
void rst() {
	for (int i=1; i<tim; i++) {
		rmq[i][0]=dlist[i];
	}
	for (int j=1; j<22; j++)
		for (int i=1; i+(1<<j)-1<tim; i++) {
			rmq[i][j]=mn(rmq[i][j-1], rmq[i+(1<<j-1)][j-1]);
		}
}
int lca(int a, int b) {
	a=fap[a];
	b=fap[b];
	int u;
	if (b<a) {
		u=a;
		a=b;
		b=u;
	}
	u=b-a+1;
	u=loog(u);
	return mn(rmq[a][u], rmq[b-(1<<u)+1][u]);
}
//
int main() {
	fin >>n >>m;
	int a, b, c;
	for (int i=0; i<m; i++) {
		fin >>a >>b >>c;
		mp[a].push_back(make_pair(b, c));
		mp[b].push_back(make_pair(a, c));
	}
	DFS(1, 0, 0);
	rst();
	fin >>q;
	for (int i=0; i<q; i++) {
		fin >>a >>b;
		int u=dlth[a]+dlth[b]-2*dlth[lca(a, b)];
		if (u>0)
			fout <<dlth[a]+dlth[b]-2*dlth[lca(a, b)] <<endl;
	}
	return 0;
}
//UBWH