hdu 2586 How far away ？ (LCA)

http://acm.hdu.edu.cn/showproblem.php?pid=2586

　　题意是给出一棵树，求两点之间的距离。

　　经典LCA的题，在hdu那里无意中看到的。做法是dfs出一个先根遍历的路径，然后对路径求RMQ，当然，也可以用线段树维护。之后就是对每个询问输出dis[u]+dis[v]-dis[lca(u,v)]*2的值即可。

代码如下：

  1 //#pragma comment(linker, "/STACK:102400000,102400000")
  2 
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <algorithm>
  6 #include <vector>
  7 #include <cmath>
  8 #include <iostream>
  9 
 10 using namespace std;
 11 
 12 const int N = 111111;
 13 const int M = 44444;
 14 int rmq[18][N];
 15 
 16 void buildRMQ(int n, int *arr) {
 17     for (int i = 0; i < n; i++) rmq[0][i] = arr[i];
 18     for (int len = 1; (1 << len) <= n; len++) {
 19         for (int i = 0; i <= n - len; i++) {
 20             rmq[len][i] = min(rmq[len - 1][i], rmq[len - 1][i + (1 << len - 1)]);
 21         }
 22     }
 23 }
 24 
 25 int queryRMQ(int l, int r) {
 26     if (l > r) swap(l, r);
 27     int depth;
 28     for (depth = 0; (1 << depth + 1) <= r - l; depth++) ;
 29     return min(rmq[depth][l], rmq[depth][r - (1 << depth) + 1]);
 30 }
 31 
 32 //int test[10] = { 10, 3, 9, 5, 1, 9, 10, 11, 6, 3};
 33 //int main() {
 34 //    buildRMQ(10, test);
 35 //    for (int i = 0; i <= 4; i++) {
 36 //        for (int j = 0; j < 10; j++) {
 37 //            cout << rmq[i][j] << ' ';
 38 //        }
 39 //        cout << endl;
 40 //    }
 41 //    cout << queryRMQ(2, 5) << endl;
 42 //    cout << queryRMQ(6, 8) << endl;
 43 //    return 0;
 44 //}
 45 
 46 #define MPR make_pair
 47 #define PB push_back
 48 
 49 typedef pair<int, int> PII;
 50 vector<PII> rel[M];
 51 bool vis[M];
 52 int dis[M], path[N], id[M], pLen;
 53 
 54 void dfs(int x) {
 55     vis[x] = true;
 56     int sz = rel[x].size();
 57     path[pLen] = x;
 58     id[x] = pLen++;
 59     for (int i = 0, t; i < sz; i++) {
 60         t = rel[x][i].first;
 61         if (vis[t]) continue;
 62         dis[t] = dis[x] + rel[x][i].second;
 63         dfs(t);
 64         path[pLen++] = x;
 65     }
 66 }
 67 
 68 int query(int x, int y) {
 69     int t = queryRMQ(id[x], id[y]);
 70     return dis[x] - dis[t] + dis[y] - dis[t];
 71 }
 72 
 73 int main() {
 74 //    freopen("in", "r", stdin);
 75     int n, m, T;
 76     while (~scanf("%d", &T)) {
 77         while (T-- && ~scanf("%d%d", &n, &m)) {
 78             for (int i = 1; i <= n; i++) {
 79                 rel[i].clear();
 80                 vis[i] = false;
 81             }
 82             int x, y, c;
 83             for (int i = 1; i < n; i++) {
 84                 scanf("%d%d%d", &x, &y, &c);
 85 //                printf("%d %d %d...\n", x, y, c);
 86                 rel[x].PB(MPR(y, c));
 87                 rel[y].PB(MPR(x, c));
 88             }
 89             pLen = 0;
 90             dis[1] = 0;
 91             dfs(1);
 92 //            for (int i = 0; i < pLen; i++) cout << path[i] << ' '; cout << endl;
 93 //            for (int i = 0; i < pLen; i++) cout << dis[i] << ' '; cout << endl;
 94             buildRMQ(pLen, path);
 95             for (int i = 0; i < m; i++) {
 96                 scanf("%d%d", &x, &y);
 97                 printf("%d\n", query(x, y));
 98             }
 99         }
100     }
101     return 0;
102 }

View Code

——written by Lyon