[关闭]
@Chilling 2017-02-18T15:42:09.000000Z 字数 2751 阅读 954

SPOJ-913: Query on a tree II(倍增LCA)

LCA


Description

You are given a tree (an undirected acyclic connected graph) with N nodes, and edges numbered 1, 2, 3...N-1. Each edge has an integer value assigned to it, representing its length.

We will ask you to perfrom some instructions of the following form:

Path from node 4 to node 6 is 4 -> 2 -> 1 -> 3 -> 6
DIST 4 6 : answer is 5 (1 + 1 + 1 + 2 = 5)
KTH 4 6 4 : answer is 3 (the 4-th node on the path from node 4 to node 6 is 3)

Input

The first line of input contains an integer t, the number of test cases (t <= 25). t test cases follow.

For each test case:

Output

For each "DIST" or "KTH" operation, write one integer representing its result.

Print one blank line after each test.

Example

Input
1
6
1 2 1
2 4 1
2 5 2
1 3 1
3 6 2
DIST 4 6
KTH 4 6 4
DONE

Output
5
3

题意: t组数据,给出一个无向图,DIST询问两点之间的距离,KTH询问两点之间的第k个点,DONE结束。

分析: 两点在图上的距离,连线一定经过他们的最近公共祖先(LCA),因此两点之间的距离即为dis[u]+dis[v]-2*dis[LCA(u,v)]
找u,v之间的第k个点,首先要知道该点是在LCA(u,v)的左边还是右边,然后以u点或者v点向上倍增得到第k个点。
为什么不以LCA(u,v)向下找?向下可能会遇到很多分支,而以一点向上找只有一条路径。


  1. #include<stdio.h>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<string.h>
  5. #define maxn 10005
  6. using namespace std;
  7. int n;
  8. int dep[maxn]; //深度
  9. int dis[maxn];
  10. int fa[maxn][15];//2^14>10000,各点向上跳2^i到达的点
  11. struct node
  12. {
  13. int en,val;
  14. node(int enn=0,int vall=0)
  15. {
  16. en=enn;
  17. val=vall;
  18. }
  19. };
  20. vector<node> V[maxn];
  21. void clr()
  22. {
  23. memset(dep,0,sizeof(dep));
  24. memset(dis,0,sizeof(dis));
  25. memset(fa,0,sizeof(fa));
  26. for(int i=0;i<=n;i++)
  27. V[i].clear();
  28. }
  29. void dfs(int u,int f,int d)//深度
  30. {
  31. fa[u][0]=f;
  32. for(int i=1;i<15;i++)
  33. fa[u][i]=fa[fa[u][i-1]][i-1];
  34. dep[u]=d;
  35. for(int i=0;i<V[u].size();i++)
  36. {
  37. node v=V[u][i];
  38. if(v.en==f) continue;
  39. dis[v.en]=dis[u]+v.val;
  40. dfs(v.en,u,d+1);
  41. }
  42. }
  43. int LCA(int u,int v)
  44. {
  45. if(dep[u]>dep[v])
  46. swap(u,v); //u浅v深
  47. for(int i=0;i<15;i++) //使等深度
  48. if((dep[v]-dep[u])>>i&1)
  49. v=fa[v][i];
  50. if(u==v) return u;
  51. for(int i=14;i>=0;i--) //同时向上跳
  52. {
  53. if(fa[u][i]!=fa[v][i])
  54. {
  55. u=fa[u][i];
  56. v=fa[v][i];
  57. }
  58. }
  59. return fa[u][0];
  60. }
  61. int kth(int u,int v,int k)
  62. {
  63. int ans;
  64. int lca=LCA(u,v);
  65. int cnt=dep[u]+dep[v]-2*dep[lca]+1; //u到v数字个数
  66. if(dep[u]-dep[lca]+1==k)
  67. return lca;
  68. else if(dep[u]-dep[lca]+1<k)//在lca右边
  69. {
  70. k=cnt-k;//跳的步数
  71. u=v;
  72. }
  73. else k--;//左边
  74. for(int i=0;i<15;i++)
  75. if(k&(1<<i))
  76. u=fa[u][i];
  77. return u;
  78. }
  79. int main()
  80. {
  81. int t;
  82. int a,b,c;
  83. char s[9];
  84. scanf("%d",&t);
  85. while(t--)
  86. {
  87. clr();
  88. scanf("%d",&n);
  89. for(int i=1;i<n;i++)
  90. {
  91. scanf("%d%d%d",&a,&b,&c);
  92. V[a].push_back(node(b,c));
  93. V[b].push_back(node(a,c));
  94. }
  95. dfs(1,0,1);
  96. while(1)
  97. {
  98. scanf("%s",s);
  99. if(s[1]=='I')
  100. {
  101. scanf("%d%d",&a,&b);
  102. printf("%d\n",dis[a]+dis[b]-2*dis[LCA(a,b)]);
  103. }
  104. else if(s[1]=='T')
  105. {
  106. int ans;
  107. scanf("%d%d%d",&a,&b,&c);
  108. printf("%d\n",kth(a,b,c));
  109. }
  110. else break;
  111. }
  112. }
  113. return 0;
  114. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注