hdu2586(带权LCA)

题意： 给定 n − 1 n-1 n−1个边的边权， m m m次询问，每次询问任意两点的最短路。

题解： 带权LCA模板。预处理时一并处理两点间最短路即可。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1e5 + 10; 
const int M = N << 1;
const int Mdep = 20;
int T, n, m;

int dep[N], dist[N];
int f[N][Mdep + 1];

int h[N], e[M], w[M], ne[M], idx;
void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int lg[N];
void init_lg() {
	for(int i = 1; i < N; i++)
		lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
}

void dfs(int u, int fa) {
	f[u][0] = fa;
	dep[u] = dep[fa] + 1;
	
	for(int i = 1; i <= lg[dep[u]]; i++)
		f[u][i] = f[f[u][i - 1]][i - 1];
	
	for(int i = h[u]; i != -1; i = ne[i]) {
		int v = e[i];
		if(v == fa) continue;
		dist[v] = dist[u] + w[i];
		dfs(v, u);
	}
}

int lca(int a, int b) {
	if(dep[a] < dep[b]) swap(a, b);
	for(int k = Mdep; k >= 0; k--)
		if(dep[f[a][k]] >= dep[b]) a = f[a][k];
	if(a == b) return a;
	for(int k = Mdep; k >= 0; k--)
		if(f[a][k] != f[b][k]) a = f[a][k], b = f[b][k];
	return f[a][0];
}

void init() {
	memset(h, -1, sizeof h);
	idx = 0; dist[1] = 0;
}

int main()
{
	init_lg();
	scanf("%d", &T);
	while(T--) {
		init();
		scanf("%d%d", &n, &m);
		for(int i = 1; i < n; i++) { 
			int a, b, c;
			scanf("%d%d%d", &a, &b, &c);
			add(a, b, c), add(b, a, c);
		} 
		
		dfs(1, 0);
		
		for(int i = 1; i <= m; i++) {
			int x, y;
			scanf("%d%d", &x, &y);
			int anc = lca(x, y);
			printf("%d\n", dist[x] + dist[y] - 2 * dist[anc]);
		}
	}
	
	return 0;
}