SPOJ 913 Query on a tree II ( 树链剖分 + 倍增 )

举报
Linux猿 发表于 2021/08/05 01:44:26 2021/08/05
【摘要】 题目链接~~> 做题感悟:感觉又充实了一些。 解题思路:树链剖分 + 倍增      开始看时,第一问还好,第二问就不知道怎么解了。其实这两问都可以用倍增法解决。                先解释一下我理解的倍增 :记录 u 结点的 第 2 ^...

题目链接~~>

做题感悟:感觉又充实了一些。

解题思路:树链剖分 + 倍增

     开始看时,第一问还好,第二问就不知道怎么解了。其实这两问都可以用倍增法解决。

               先解释一下我理解的倍增 :记录 u 结点的 第 2 ^ i 个祖先,然后求u 的第 k 个祖先的时候,就相当于用 2 ^ i 去组合 k ,不断向上,一直到达第 k 个节点,其实每次更新的时k 的二进制中为 1 的位置。如下图,计算 u 的第 5 个祖先结点(这里不包括 u),先到达 u' 节点,然后再从 u' ,到 u'' (5 的二进制 101) 。会倍增算法后就好做了,计算第一问的时候 dis = dis[ u ] + dis[v] - 2 * dis[ LCA(u ,v)] ,第二问先判断一下要求的点在 u 到交点的链上还是在 v 到交点的链上然后再结合倍增做就ok了。

代码:


  
  1. #include<iostream>
  2. #include<sstream>
  3. #include<map>
  4. #include<cmath>
  5. #include<fstream>
  6. #include<queue>
  7. #include<vector>
  8. #include<sstream>
  9. #include<cstring>
  10. #include<cstdio>
  11. #include<stack>
  12. #include<bitset>
  13. #include<ctime>
  14. #include<string>
  15. #include<cctype>
  16. #include<iomanip>
  17. #include<algorithm>
  18. using namespace std ;
  19. #define INT long long int
  20. #define L(x) (x * 2)
  21. #define R(x) (x * 2 + 1)
  22. const int INF = 0x3f3f3f3f ;
  23. const double esp = 0.0000000001 ;
  24. const double PI = acos(-1.0) ;
  25. const INT mod = 1000000007 ;
  26. const int MY = 1400 + 5 ;
  27. const int MX = 20000 + 5 ;
  28. int num ,S = 20 ,n ;
  29. int head[MX] ,dep[MX] ,dis[MX] ,p[MX][30] ;
  30. struct NODE
  31. {
  32. int v ,w ,next ;
  33. }E[MX] ;
  34. void addedge(int u ,int v ,int w)
  35. {
  36. E[num].v = v ; E[num].w = w ; E[num].next = head[u] ; head[u] = num++ ;
  37. E[num].v = u ; E[num].w = w ; E[num].next = head[v] ; head[v] = num++ ;
  38. }
  39. void dfs_find(int u ,int fa ,int w) // 处理深度、距离
  40. {
  41. dep[u] = dep[fa] + 1 ;
  42. dis[u] = w ;
  43. p[u][0] = fa ;
  44. for(int i = 1 ;i <= S ; ++i) // 处理祖先
  45. p[u][i] = p[p[u][i-1]][i-1] ;
  46. for(int i = head[u] ;i != -1 ;i = E[i].next)
  47. {
  48. int v = E[i].v ;
  49. if(v == fa) continue ;
  50. dfs_find(v ,u ,w + E[i].w) ;
  51. }
  52. }
  53. int LCA(int u ,int v) // 计算公共交点
  54. {
  55. if(dep[u] > dep[v]) swap(u ,v) ; // u 的深度小于等于 v
  56. if(dep[u] < dep[v]) // 处理成同一深度
  57. {
  58. int d = dep[v] - dep[u] ; // 深度差
  59. for(int i = 0 ;i < S ; ++i)
  60. if(d&(1<<i))
  61. v = p[v][i] ;
  62. }
  63. if(u != v) // 已经变成同一深度
  64. {
  65. for(int i = S ;i >= 0 ; --i)
  66. if(p[u][i] != p[v][i])
  67. {
  68. u = p[u][i] ;
  69. v = p[v][i] ;
  70. }
  71. u = p[u][0] ;
  72. v = p[v][0] ;
  73. }
  74. return u ;
  75. }
  76. int cunt(int u ,int k) // 计算 u 的第 k 个节点
  77. {
  78. for(int i = 0 ;i < S ; ++i)
  79. if(k&(1<<i))
  80. u = p[u][i] ;
  81. return u ;
  82. }
  83. int Query(int u ,int v ,int k) // 从 u 到 v 的路径上的第 k 个节点
  84. {
  85. int z = LCA(u ,v) ; // 公共交点
  86. if(dep[u] - dep[z] + 1 >= k) // 在 u 的这条链上
  87. return cunt(u ,k-1) ;
  88. else // 在 v 的这条线上
  89. {
  90. k -= dep[u] - dep[z] ;
  91. k = dep[v] - dep[z] - k + 1 ;
  92. return cunt(v ,k) ;
  93. }
  94. }
  95. int main()
  96. {
  97. //freopen("input.txt" ,"r" ,stdin) ;
  98. char s[10] ;
  99. int Tx ,u ,v ,w ,k ;
  100. scanf("%d" ,&Tx) ;
  101. while(Tx--)
  102. {
  103. scanf("%d" ,&n) ;
  104. num = 0 ;
  105. memset(head ,-1 ,sizeof(head)) ;
  106. for(int i = 1 ;i < n ; ++i)
  107. {
  108. scanf("%d%d%d" ,&u ,&v ,&w) ;
  109. addedge(u ,v ,w) ;
  110. }
  111. dep[1] = 0 ;
  112. dfs_find(1 ,1 ,0) ;
  113. while(scanf("%s" ,s) && strcmp(s ,"DONE"))
  114. {
  115. if(s[0] == 'D') // 求任意两点之间的距离
  116. {
  117. scanf("%d%d" ,&u ,&v) ;
  118. printf("%d\n" ,dis[u] + dis[v] - 2 *dis[LCA(u ,v)]) ;
  119. }
  120. else // 询问第 k 个节点
  121. {
  122. scanf("%d%d%d" ,&u ,&v ,&k) ;
  123. printf("%d\n" ,Query(u ,v ,k)) ;
  124. }
  125. }
  126. }
  127. return 0 ;
  128. }




文章来源: blog.csdn.net,作者:Linux猿,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/nyist_zxp/article/details/40828981

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。