题目：给一棵带权树，然后让你求任意两点之间的距离。
思路：tarjan一边dfs求出dis[i]每个点到根的距离，ans[i]第i组查询的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, m, 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 a, b, val; 73 char tc[10]; 74 while(scanf("%d%d", &n, &m)!=EOF){ 75 init(); 76 for(int i=0; i<m; i++) { 77 scanf("%d%d%d", &a, &b, &val); 78 gets(tc); 79 Map[a].PB(MP(b, val)); 80 Map[b].PB(MP(a, val)); 81 } 82 scanf("%d", &q); 83 for(int i=0; i<q; i++){ 84 scanf("%d%d", &a, &b); 85 qv[i] = MP(a, b); 86 que[a].PB(MP(b, i)); 87 que[b].PB(MP(a, i)); 88 } 89 dis[1] = 0; 90 tarjan(1); 91 for(int i=0; i<q; i++){ 92 printf("%d ", dis[qv[i].first]+dis[qv[i].second]-2*dis[ans[i]]); 93 } 94 } 95 return 0; 96 }