题目：给一颗带权树，让你求任意两点之间距离。有若干询问。
思路：求出lca ans = dis[u]+dis[v]-2*dis[lca]。
代码如下：
1 /************************************************** 2 * Author : xiaohao Z 3 * Blog : http://www.cnblogs.com/shu-xiaohao/ 4 * Last modified : 2014-02-09 09:18 5 * Filename : hdu_2586.cpp 6 * Description : 7 * ************************************************/ 8 9 #include <iostream> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <cmath> 14 #include <algorithm> 15 #include <queue> 16 #include <stack> 17 #include <vector> 18 #include <set> 19 #include <map> 20 #define MP(a, b) make_pair(a, b) 21 #define PB(a) push_back(a) 22 23 using namespace std; 24 typedef long long ll; 25 typedef pair<int, int> pii; 26 typedef pair<unsigned int,unsigned int> puu; 27 typedef pair<int, double> pid; 28 typedef pair<ll, int> pli; 29 typedef pair<int, ll> pil; 30 31 const int INF = 0x3f3f3f3f; 32 const double eps = 1E-6; 33 const int LEN = 40000+10; 34 vector<pii> Map[LEN], que[LEN]; 35 pii qv[LEN]; 36 int n, q, vis[LEN], fa[LEN], ancestor[LEN], ans[LEN], dis[LEN]; 37 38 void init(){ 39 for(int i=0; i<LEN; i++) { 40 Map[i].clear(); 41 que[i].clear(); 42 fa[i] = i; 43 } 44 memset(vis, 0, sizeof vis); 45 memset(ancestor, 0, sizeof ancestor); 46 } 47 //UFSet 48 int Find(int x){return fa[x] == x ? x : fa[x] = Find(fa[x]);} 49 void Union(int a, int b){int pa = Find(a), pb = Find(b);if(pa != pb) fa[pa] = pb;} 50 51 void tarjan(int u){ 52 ancestor[u] = u; 53 vis[u] = 1; 54 for(int i=0; i<Map[u].size(); i++){ 55 int v = Map[u][i].first; 56 if(vis[v]) continue; 57 dis[v] = dis[u] + Map[u][i].second; 58 tarjan(v); 59 Union(u, v); 60 ancestor[Find(u)] = u; 61 } 62 for(int i=0; i<que[u].size(); i++){ 63 int v = que[u][i].first, idx = que[u][i].second; 64 if(vis[v])ans[idx] = ancestor[Find(v)]; 65 } 66 } 67 68 int main() 69 { 70 // freopen("in.txt", "r", stdin); 71 72 int T, a, b, val; 73 scanf("%d", &T); 74 while(T--){ 75 init(); 76 scanf("%d%d", &n, &q); 77 for(int i=0; i<n-1; i++) { 78 scanf("%d%d%d", &a, &b, &val); 79 Map[a].PB(MP(b, val)); 80 Map[b].PB(MP(a, val)); 81 } 82 for(int i=0; i<q; i++){ 83 scanf("%d%d", &a, &b); 84 qv[i] = MP(a, b); 85 que[a].PB(MP(b, i)); 86 que[b].PB(MP(a, i)); 87 } 88 dis[1] = 0; 89 tarjan(1); 90 for(int i=0; i<q; i++){ 91 printf("%d ", dis[qv[i].first]+dis[qv[i].second]-2*dis[ans[i]]); 92 } 93 } 94 return 0; 95 }