记录编号	173569	评测结果	AAAAAAAAAA
题目名称	[USACO Feb04]距离咨询	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.227 s
提交时间	2015-07-29 11:05:55	内存使用	7.62 MiB

# include <cstdio>
# include <cstring>

using namespace std;

const int MAXN = 40001;

int n,m,tot,w;
int head[MAXN];
int deep[MAXN];
int pre[MAXN][20];
int father[MAXN][20];

struct Edge {
	int v,next,w;
} e[MAXN << 1];

void swap(int &a,int &b) {
	a^=b;
	b^=a;
	a^=b;
}

void add(int u,int v,int w) {
	e[++tot].v = v;
	e[tot].w = w;
	e[tot].next = head[u];
	head[u] = tot;
}

void dfs(int x) {
	for(int i = head[x]; i; i = e[i].next) {
		int v = e[i].v;
		if(!deep[v]) {
			deep[v] = deep[x] + 1;
			father[v][0] = x;
			pre[v][0] = e[i].w;
			dfs(v);
		}
	}
}

int LCA(int x,int y) {
	int i,j;
	int ans = 0;
	if(deep[x] < deep[y])
		swap(x,y);
	for(i = 0; (1 << i) <= deep[x]; ++i);
	i--;
	for(j = i; j >= 0; j--)
		if(deep[x] - (1 << j) >= deep[y]) {
			ans += pre[x][j];
			x = father[x][j];
		}
	if(x == y)	return ans;
	for(j=i; j>=0; j--)
		if(father[x][j] != father[y][j]) {
			ans += pre[x][j] + pre[y][j];
			x = father[x][j];
			y = father[y][j];
		}
	ans = ans + pre[x][0] + pre[y][0];
	return ans;
}

int main() {
	freopen("dquery.in","r",stdin);
	freopen("dquery.out","w",stdout);
	int i,j,u,v,w;
	char pos;
	deep[1] = 1;
	scanf("%d%d",&n,&m);
	for(i = 1; i <= m; ++i) {
		scanf("%d%d%d",&u,&v,&w);
		pos = getchar();
		pos = getchar();
		add(u,v,w);
		add(v,u,w);
	}
	dfs(1);
	for(j = 1; (1 << j) <= n; ++j)
		for(i = 1; i <= n; ++i) {
			father[i][j] = father[father[i][j - 1]][j - 1];
			pre[i][j] = pre[i][j - 1] + pre[father[i][j - 1]][j - 1];
		}
	scanf("%d",&w);	
	while(w--) {
		scanf("%d%d",&u,&v);
		printf("%d\n",LCA(u,v));
	}
	return 0;
}