记录编号	232505	评测结果	AAAAAAAAAA
题目名称	[USACO Feb04]距离咨询	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.539 s
提交时间	2016-03-01 19:58:16	内存使用	6.05 MiB

//KZNS
#include <fstream>
#include <vector>
using namespace std;
//
ifstream fin ("dquery.in");
ofstream fout ("dquery.out");
//
class poi {
public:
	int t, v;
};
//
int n, m;
vector<poi> mp[40003];
int ys[40003]={0};
int dpls[40003]={0};
int dfsdp[40003]={0};
int dfsls[80003]={0}, lsu=1;
int mn[80003][17]={0};
//
poi npoi(int t, int v) {
	poi u;
	u.t=t;
	u.v=v;
	return u;
}
void DFS(int x, int dp, int ddp) {
	dfsls[lsu]=x;
	ys[x]=lsu++;
	dpls[x]=dp;
	dfsdp[x]=ddp;
	for (int i=0; i<mp[x].size(); i++) {
		if (!ys[mp[x][i].t]) {
			DFS(mp[x][i].t, dp+mp[x][i].v, ddp+1);
			dfsls[lsu++]=x;
		}
	}
}
void RMQST() {
	for (int i=1; i<lsu; i++)
		mn[i][0]=dfsls[i];
	for (int j=1; j<17; j++)
		for (int i=1; i+(1<<j)-1<lsu; i++) {
			if (dfsdp[mn[i][j-1]]<dfsdp[mn[i+(1<<j-1)][j-1]])
				mn[i][j]=mn[i][j-1];
			else
				mn[i][j]=mn[i+(1<<j-1)][j-1]; 
		}
}
inline int loog(int k) {
	int u=1;
	for (int i=0; true; i++)
		if (k<(u<<=1))
			return i;
}
int lca(int a, int b) {
	int l=ys[a], r=ys[b], u;
	if (r<l) {
		u=l;
		l=r;
		r=u;
	}
	u=loog(r-l+1);
	if (dfsdp[mn[l][u]]<dfsdp[mn[r-(1<<u)+1][u]])
		return mn[l][u];
	else
		return mn[r-(1<<u)+1][u];
}
//
int main() {
	fin >>n >>m;
	int a, b, v;
	char c;
	for (int i=0; i<m; i++) {
		fin >>a >>b >>v >>c;
		mp[a].push_back(npoi(b, v));
		mp[b].push_back(npoi(a, v));
	}
	DFS(1, 0, 1);
	RMQST();
	fin >>m;
	for (int i=0; i<m; i++) {
		fin >>a >>b;
		fout <<dpls[a]+dpls[b]-2*dpls[lca(a, b)] <<endl;
	}
	return 0;
}
//UBWH