HDU 2586 How far away ？ (离线LCA Tarjan算法模板) - Tc_To_Top的专栏 - 博客频道 - CSDN.NET

HDU 2586 How far away ？ (离线LCA Tarjan算法模板) - Tc_To_Top的专栏 - 博客频道 - CSDN.NET
Problem Description

There are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this "How far is it if I want to go from house A to house B"? Usually it hard to answer. But luckily int this village the answer is always unique, since the roads are built in the way that there is a unique simple path("simple" means you can't visit a place twice) between every two houses. Yout task is to answer all these curious people.

Input

First line is a single integer T(T<=10), indicating the number of test cases.
  For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n.
  Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.

Output

For each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case.

Tarjan
http://www.cppblog.com/CodeStream/archive/2011/03/24/142651.aspx
http://blog.csdn.net/tc_to_top/article/details/43941007

DFS
题目的意思就是给定一些houses的编号，及这些编号房子之间的距离，然后有m次询问，每次询问给出两个房子的编号，要求给出这两个房子的最小距离。这张图是树图，也就是总共N个点N-1条边，然后能把所有点全部连通。本身分析题目很容易知道本题就是求最小公共祖先的问题，首先确定一个根节点，然后DFS遍历一遍计算此根节点到所有节点的距离，然后可以用离线的tarjan算法，来找到两个询问节点a和b的最近公共祖先c，然后要求的结果就是dist[a] - dist[c] + dist[b] - dist[c]，意思很好理解，画棵树看看就可以了，而且这种思路也是很容易想到的。这里用了一下非递归的DFS直接来求，每次询问直接使用DFS求亮点之间的距离
http://blog.csdn.net/iaccepted/article/details/43072689
http://blog.csdn.net/hnust_xiehonghao/article/details/9071803

1. struct haha  
2. {  
3.     int pos;  
4.     int val;  
5. }temp,q;  
6. vector<struct haha>a[44444];  
7. int n,m,flag,e,vis[444444];  
8. void DFS(int s,int ans)  
9. {  
10.     //printf("s=%d\n",s);  
11.     int size,i;  
12.     if(vis[s]) return ;  
13.     if(flag) return ;  
14.     if(s==e) {printf("%d\n",ans);flag=1;return;}  
15.      if(a[s].empty())  return ;  
16.      else  
17.      {  
18.     vis[s]=1;  
19.      size=a[s].size();  
20.      for(i=0;i<size;i++)  
21.         DFS(a[s][i].pos,ans+a[s][i].val);  
22.      vis[s]=0;  
23.      }  
24. }  
25. int main()  
26. {  
27.     int cas;  
28.     scanf("%d",&cas);  
29.     while(cas--)  
30.     {  
31.         int i,j,x,y,z;  
32.         scanf("%d %d",&n,&m);  
33.         for(i=0;i<n-1;i++)  
34.         {  
35.                 scanf("%d %d %d",&x,&y,&z);  
36.                 q.pos=y;q.val=z;  
37.                 a[x].push_back(q);  
38.                 q.pos=x;q.val=z;  
39.                 a[y].push_back(q);  
40.         }  
41.         for(j=0;j<m;j++)  
42.         {  
43.             memset(vis,0,sizeof(vis));  
44.             flag=0;  
45.             int s;  
46.             scanf("%d %d",&s,&e);  
47.             DFS(s,0);  
48.         }  
49.         for(i=0;i<n;i++)  
50.         {  
51.             a[i].clear();  
52.         }  
53.     }  
54.       return 0;  
55. }  

How far away ？（LCA 在线算法RMQ）
LCA。RMQ 的在线算法，任何一个根为起点都可以，dfs 的时候顺便用 dis 记录到根的距离，求出 a 和 b 的 LCA c，则距离等于 dis [ a ] + dis [ b ] - 2 X dis [ c ]。因为 RMQ 数组的长度开小了，所以 WA 了很多遍。

1. int n, ind;  
2. int next[EMAX], fir[VMAX], w[EMAX], v[EMAX];  
3.   
4. int k;  
5. int dis[VMAX], vs[VMAX * 5], dep[VMAX * 5], id[VMAX];  
6. bool vis[VMAX];  
7.   
8. int dp[VMAX * 5][25];  
9.   
10. void init () {  
11.     ind = k = 0;  
12.     memset(fir, -1, sizeof(fir));  
13.     memset(vis, 0, sizeof(vis));  
14. }  
15.   
16. void add_edge (int f, int t, int val) {  
17.     v[ind] = t;  
18.     w[ind] = val;  
19.     next[ind] = fir[f];  
20.     fir[f] = ind;  
21.     ++ind;  
22. }  
23.   
24. void dfs (int x, int d) {  
25.     id[x] = k;  
26.     vs[k] = x;  
27.     dep[k++] = d;  
28.     vis[x] = 1;  
29.   
30.     for (int e = fir[x]; e != -1; e = next[e]) {  
31.         int V = v[e];  
32.         if (!vis[V]) {  
33.             dis[V] = dis[x] + w[e];  
34.             dfs(V, d + 1);  
35.             vs[k] = x;  
36.             dep[k++] = d;  
37.         }  
38.     }  
39. }  
40.   
41. void RMQ_init () {  
42.     for (int i = 0; i < k; ++i) dp[i][0] = i;  
43.   
44.     for (int j = 1; (1 << j) <= k; ++j) {  
45.         for (int i = 0; i + (1 << j) - 1 < k; ++i) {  
46.             int a = dp[i][j - 1];  
47.             int b = dp[i + (1 << (j - 1))][j - 1];  
48.             if (dep[a] > dep[b]) dp[i][j] = b;  
49.             else dp[i][j] = a;  
50.         }  
51.     }  
52. }  
53.   
54. int RMQ (int L, int R) {  
55.     int len = 0;  
56.     while ((1 << (len + 1)) <= (R - L + 1)) ++len;  
57.   
58.     int a = dp[L][len];  
59.     int b = dp[R - (1 << len) + 1][len];  
60.   
61.     if (dep[a] > dep[b]) return b;  
62.     return a;  
63. }  
64.   
65. int LCA (int a, int b) {  
66.     int L = min(id[a], id[b]);  
67.     int R = max(id[a], id[b]);  
68.     int Min = RMQ(L, R);  
69.     return vs[Min];  
70. }  
71.   
72. int main () {  
73.   
74.     int T;  
75.     scanf("%d", &T);  
76.   
77.     while (T--) {  
78.         init();  
79.   
80.         int m;  
81.         scanf("%d%d", &n, &m);  
82.   
83.         for (int i = 1; i <= n - 1; ++i) {  
84.             int a, b, val;  
85.             scanf("%d%d%d", &a, &b, &val);  
86.             add_edge(a, b, val);  
87.             add_edge(b, a, val);  
88.         }  
89.   
90.         dfs (1, 1);  
91.   
92.         RMQ_init();  
93.   
94.         while (m--) {  
95.             int a, b;  
96.             scanf("%d%d", &a, &b);  
97.   
98.             int node = LCA(a, b);  
99.             printf("%d\n", dis[a] + dis[b] - 2 * dis[node]);  
100.         }  
101.   
102.     }  
103.   
104.     return 0;  
105. }  

Read full article from HDU 2586 How far away ？ (离线LCA Tarjan算法模板) - Tc_To_Top的专栏 - 博客频道 - CSDN.NET