Description
N头牛（2<=n<=1000）别人被标记为1到n，在同样被标记1到n的n块土地上吃草，第i头牛在第i块牧场吃草。 这n块土地被n-1条边连接。 奶牛可以在边上行走，第i条边连接第Ai，Bi块牧场，第i条边的长度是Li（1<=Li<=10000）。 这些边被安排成任意两头奶牛都可以通过这些边到达的情况，所以说这是一棵树。 这些奶牛是非常喜欢交际的，经常会去互相访问,他们想让你去帮助他们计算Q(1<=q<=1000)对奶牛之间的距离。
Input
*第一行：两个被空格隔开的整数：N和Q
*第二行到第n行：第i+1行有两个被空格隔开的整数：AI，BI，LI
*第n+1行到n+Q行：每一行有两个空格隔开的整数：P1，P2，表示两头奶牛的编号。
Output
*第1行到第Q行：每行输出一个数，表示那两头奶牛之间的距离。
Sample Input
4 2
2 1 2
4 3 2
1 4 3
1 2
3 2
Sample Output
2
7
HINT
Source
资格赛
lca
#include <iostream> #include <cstdio> using namespace std; const int SZ = 1010; struct Edge { int f, t, d; }es[SZ << 1]; int first[SZ << 1], nxt[SZ << 1], tot = 1; int depth[SZ], fa[SZ], dis[SZ], jump[SZ][20]; void build(int f, int t, int d) { es[++tot] = (Edge){f, t ,d}; nxt[tot] = first[f]; first[f] = tot; } void dfs(int u, int f) { depth[u] = depth[f] + 1; fa[u] = f; jump[u][0] = f; for(int i = 1; i <= 16; i++) jump[u][i] = jump[jump[u][i - 1]][i - 1]; for(int i = first[u]; i; i = nxt[i]) { int v = es[i].t; if(v == f) continue; dis[v] = dis[u] + es[i].d; dfs(v, u); } } int lca(int l, int r) { if(depth[l] < depth[r]) swap(l, r); int t = depth[l] - depth[r]; for(int i = 0; i <= 16; i++) if(t & (1 << i)) l = jump[l][i]; for(int i = 16; i >= 0; i--) if(jump[l][i] != jump[r][i]) l = jump[l][i], r = jump[r][i]; if(l == r) return l; return jump[l][0]; } int main() { int n, q; scanf("%d%d", &n, &q); int f, t, d; for(int i = 1; i < n; i++) { scanf("%d%d%d", &f, &t, &d); build(f, t, d); build(t, f, d); } dfs(1, 0); for(int i = 1; i <= q; i++) { scanf("%d%d", &f, &t); int F = lca(f, t); int ans = dis[f] + dis[t] - 2 * dis[F]; printf("%d\n", ans); } return 0; } 转载于:https://www.cnblogs.com/Loi-Vampire/p/6017040.html
相关资源：JAVA上百实例源码以及开源项目