记录编号	405824	评测结果	AAAAAAAAAA
题目名称	[USACO Oct08] 牧场旅行	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2017-05-17 14:42:42	内存使用	1.74 MiB

# include <bits/stdc++.h>
# define MAXN 10023
using namespace std;
inline int gn() {
	int k = 0;
	char c = getchar();
	for(; !isdigit(c); c = getchar());
	for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
	return k;
}
int n, m, dis[MAXN], dep[MAXN << 1], ver[MAXN << 1], fir[MAXN];
bool vis[MAXN];
struct edge {
	int to, w;
	edge *ne;
	inline edge() {ne = NULL;}
	inline edge(int to_, int w_, edge *ne_) {
		to = to_, w = w_, ne = ne_;
	}
}*head[MAXN];
inline void addedge(int fr, int to, int w) {
	edge *e = new edge(to, w, head[fr]);
	head[fr] = e;	
}
int tot;
void dfs(int u, int de) {
	vis[u] = 1;
	ver[++tot] = u;
	fir[u] = tot;
	dep[tot] = de;
	for(edge *e = head[u]; e; e = e->ne) {
		int v = e->to;
		if(vis[v]) continue;
		dis[v] = dis[u] + e->w;
		dfs(v, de + 1);
		ver[++tot] = u;
		dep[tot] = de;
	}
}
int dp[MAXN << 1][15];
inline void ST() {
	for(int i = 1; i <= tot; i++) {
		dp[i][0] = i;
	}
	for(int j = 1; (1 << j) <= tot; j++) {
		for(int i = 1; i + (1 << j) - 1 <= tot; i++) {
			int a = dp[i][j - 1];
			int b = dp[i + (1 << (j - 1))][j - 1];
			dp[i][j] = dep[a] < dep[b] ? a : b;
		}
	}
}
inline int RMQ(int l, int r) {
	int k = 0;
	for(; 1 << (k + 1) < r - l + 1; k++);
	int a = dp[l][k], b = dp[r - (1 << (k)) + 1][k];
	return dep[a] < dep[b] ? a : b;
}
inline int LCA(int u, int v) {
	u = fir[u];
	v = fir[v];
	if(v < u) swap(u, v);
	int res = RMQ(u, v);
	return ver[res];
} 
inline int DIS(int u, int v) {
	int lca = LCA(u, v);
	int ans = 0;
	ans = dis[u] + dis[v] - (dis[lca] << 1);
	return ans;
}
int main() {
	freopen("pwalk.in", "r", stdin);
	freopen("pwalk.out", "w", stdout);
	n = gn();
	m = gn();
	for(int i = 1; i < n; i++) {
		int x = gn();
		int y = gn();
		int z = gn();
		addedge(x, y, z);
		addedge(y, x, z);
	}
	dfs(1, 1);
	ST();
	for(int i = 1; i <= m; i++) {
		int u = gn();
		int v = gn();
		if(u == v) printf("0\n");
		else printf("%d\n", DIS(u, v));
	}

	//printf("\nver: ");
	//for(int i = 1; i <= tot; i++) cout << ver[i] << " ";
	//printf("\ndep: ");
	//for(int i = 1; i <= tot; i++) cout << dep[i] << " ";
	//printf("\ndis: ");
	//for(int i = 1; i <= n; i++) cout << dis[i] << " ";
	//printf("\nfir: ");
	//for(int i = 1; i <= n; i++) cout << fir[i] << " ";

}