题目大意：给出一张连通图，，问两个点之间的距离
解题思路：LCA裸题
Edge{int to, next, dis;}E[M];struct Question {int x, y;}Q[N];int n, m ,tot;int head[N], dist[N], f[N], LCA[N];bool vis[N];void AddEdge(int u, int v, int dis) {E[tot].to = v; E[tot].dis = dis; E[tot].next = head[u]; head[u] = tot++;u = u ^ v; v = u ^ v; u = u ^ v;E[tot].to = v; E[tot].dis = dis; E[tot].next = head[u]; head[u] = tot++;}int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}void tarjan(int u) {vis[u] = true;f[u] = u;for (int i = head[u]; i != -1; i = E[i].next) {int v = E[i].to;if (!vis[v]) {dist[v] = dist[u] + E[i].dis;tarjan(v);f[v] = u;}}for (int i = 0; i < m; i++) {if (u == Q[i].x && vis[Q[i].y])LCA[i] = find(Q[i].y);if (u == Q[i].y && vis[Q[i].x])LCA[i] = find(Q[i].x);}}void init() {memset(head, -1, sizeof(head));tot = 0;int u, v, d;scanf(“%d%d”, &n, &m);for (int i = 0; i < n – 1; i++) {scanf(“%d%d%d”, &u, &v, &d);AddEdge(u, v, d);}for (int i = 0; i < m; i++) scanf(“%d%d”, &Q[i].x, &Q[i].y);memset(vis, 0, sizeof(vis));}void solve() {dist[1] = 0;tarjan(1);for (int i = 0; i < m; i++)printf(“%d\n”, dist[Q[i].x] + dist[Q[i].y] – 2 * dist[LCA[i]]);}int main() {int test;scanf(“%d”, &test);while (test–) {init();solve();}return 0;}
孑然一身，隐入苍茫自然，自有一种孤独的意味;旅行，
