HDU 2874 Connections between cities（LCA）

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define REP(i,n)        for(int i(0); i <  (n); ++i)
 6 #define rep(i,a,b)        for(int i(a); i <= (b); ++i)
 7 #define dec(i,a,b)        for(int i(a); i >= (b); --i)
 8 #define for_edge(i,x)        for(int i = H[x]; i; i = X[i])
 9 
10 const int N    =    50000        +    10;
11 const int A    =    20        +    1;
12 
13 int father[N], List[N], deep[N], E[N], X[N], H[N], V[N];
14 int f[N][A], g[N][A];
15 bool v[N];
16 int n, m, q, x, y, z;
17 int et;
18 
19 inline void Eddedge(int a, int b, int c){
20     E[++et] = b, X[et] = H[a], H[a] = et, V[et] = c;
21     E[++et] = a, X[et] = H[b], H[b] = et, V[et] = c;
22 }
23 
24 int getfather(int x){ return father[x] ? father[x]  = getfather(father[x]) : x; } 
25 
26 int Calc(int a, int b){
27     int ret = 0;
28 
29     if (deep[a] < deep[b]) swap(a, b);
30     for (int i = 0, delta = deep[a] - deep[b]; delta; delta >>= 1, ++i)
31         if (delta & 1) ret += g[a][i], a = f[a][i];
32 
33     if (a == b) return ret;
34 
35     dec(i, 19, 0) if (f[a][i] != f[b][i]){
36         ret += g[a][i];
37         ret += g[b][i];
38         a = f[a][i];
39         b = f[b][i];
40     }
41 
42     ret += g[a][0];
43     ret += g[b][0];
44 
45     return ret;
46 }
47 
48 int main(){
49 
50     while (~scanf("%d%d%d", &n, &m, &q)){
51 
52         et = 0;
53         memset(father, 0, sizeof father);
54         memset(H, 0, sizeof H);
55 
56 
57         rep(i, 1, m){
58             scanf("%d%d%d", &x, &y, &z);Eddedge(x, y, z);
59             int fa = getfather(x), fb = getfather(y);
60             father[fa] = fb;
61         }
62 
63         int l = 0, r = 0, now = 0;
64         memset(List, 0, sizeof List);
65         memset(deep, 0, sizeof deep);
66         memset(v, false , sizeof v);
67         memset(f, 0, sizeof f);
68         memset(g, 0, sizeof g);
69 
70         rep(p, 1, n) if (!v[p]){
71             for (l = 1, r = 1, v[p] = true, List[1] = p; l <= r; ++l){
72                 now = List[l];
73                 for_edge(i, now) if (!v[E[i]]){
74                     v[E[i]] = true;
75                     f[E[i]][0] = now;
76                     g[E[i]][0] = V[i];
77                     deep[E[i]] = deep[now] + 1;
78 
79                     for (int j = 0; f[E[i]][j]; ++j)
80                         f[E[i]][j + 1] = f[f[E[i]][j]][j],
81                             g[E[i]][j + 1] = g[E[i]][j] + g[f[E[i]][j]][j];
82 
83                     List[++r] = E[i];
84                 }
85             }
86         }
87 
88         while (q--){
89             scanf("%d%d", &x, &y);
90             int fa = getfather(x), fb = getfather(y);
91             if (fa != fb) puts("Not connected"); else printf("%d
", Calc(x, y));
92         }
93 
94     }
95 
96     return 0;
97 
98 }