HYSBZ 2243 染色 (树链剖分)

举报
Linux猿 发表于 2021/08/04 23:35:08 2021/08/04
【摘要】 题目链接~~> 做题感悟:这题思路好想,调试代码调试了好久,第一次写线段树区间合并。 解题思路:              树链剖分 + 线段树区间合并        线段树的端点记录左右区间的颜色,颜色数目。合并的时候就用区间合并的思想。还要注意一点...

题目链接~~>

做题感悟:这题思路好想,调试代码调试了好久,第一次写线段树区间合并。

解题思路:

             树链剖分 + 线段树区间合并

       线段树的端点记录左右区间的颜色,颜色数目。合并的时候就用区间合并的思想。还要注意一点,在由一条链转到另一条链的时候要判断当前节点是否与父亲节点是否同一种颜色。

代码:


  
  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 __int64
  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 = 1e9 + 7 ;
  26. const int MY = 1400 + 5 ;
  27. const int MX = 100000 + 5 ;
  28. int n ,m ,idx ,num ;
  29. int head[MX] ,ti[MX] ,top[MX] ,dep[MX] ,siz[MX] ,son[MX] ,father[MX] ,g[MX] ;
  30. struct Edge
  31. {
  32. int v ,next ;
  33. }E[MX*2] ;
  34. void addedge(int u ,int v)
  35. {
  36. E[num].v = v ; E[num].next = head[u] ; head[u] = num++ ;
  37. E[num].v = u ; E[num].next = head[v] ; head[v] = num++ ;
  38. }
  39. void dfs_find(int u ,int fa)
  40. {
  41. dep[u] = dep[fa] + 1 ;
  42. siz[u] = 1 ;
  43. son[u] = 0 ;
  44. father[u] = fa ;
  45. for(int i = head[u] ;i != -1 ;i = E[i].next)
  46. {
  47. int v = E[i].v ;
  48. if(v == fa) continue ;
  49. dfs_find(v ,u) ;
  50. siz[u] += siz[v] ;
  51. if(siz[son[u]] < siz[v]) son[u] = v ;
  52. }
  53. }
  54. void dfs_time(int u ,int fa)
  55. {
  56. ti[u] = idx++ ;
  57. top[u] = fa ;
  58. if(son[u]) dfs_time(son[u] ,top[u]) ;
  59. for(int i = head[u] ;i != -1 ;i = E[i].next)
  60. {
  61. int v = E[i].v ;
  62. if(v == father[u] || v == son[u]) continue ;
  63. dfs_time(v ,v) ;
  64. }
  65. }
  66. struct node
  67. {
  68. int le ,rt ,lc ,rc ,num ,add ;
  69. }T[MX*4] ;
  70. void build(int x ,int le ,int rt)
  71. {
  72. T[x].le = le ; T[x].rt = rt ;
  73. T[x].lc = T[x].rc = T[x].add = -1 ;
  74. T[x].num = 0 ;
  75. if(le == rt) return ;
  76. int Mid = (le + rt)>>1 ;
  77. build(L(x) ,le ,Mid) ;
  78. build(R(x) ,Mid + 1 ,rt) ;
  79. }
  80. void push_down(int x)
  81. {
  82. if(T[x].add != -1)
  83. {
  84. // 左
  85. T[L(x)].lc = T[L(x)].rc = T[L(x)].add = T[x].add ; T[L(x)].num = 1 ;
  86. // 右
  87. T[R(x)].lc = T[R(x)].rc = T[R(x)].add = T[x].add ; T[R(x)].num = 1 ;
  88. T[x].add = -1 ;
  89. }
  90. }
  91. void push_up(int x)
  92. {
  93. T[x].num = T[L(x)].num + T[R(x)].num ;
  94. if(T[L(x)].rc == T[R(x)].lc)
  95. T[x].num -- ;
  96. T[x].lc = T[L(x)].lc ; T[x].rc = T[R(x)].rc ;
  97. }
  98. void update(int x ,int le ,int rt ,int w) // 更新某个区间
  99. {
  100. if(T[x].le == le && T[x].rt == rt)
  101. {
  102. T[x].add = w ;
  103. T[x].lc = w ; T[x].rc = w ; T[x].num = 1 ;
  104. return ;
  105. }
  106. push_down(x) ;
  107. int Mid = (T[x].le + T[x].rt)>>1 ;
  108. if(le > Mid) update(R(x) ,le ,rt ,w) ;
  109. else if(rt <= Mid) update(L(x) ,le ,rt ,w) ;
  110. else
  111. {
  112. update(L(x) ,le ,Mid ,w) ;
  113. update(R(x) ,Mid+1 ,rt ,w) ;
  114. }
  115. push_up(x) ;
  116. }
  117. int Query(int x ,int le ,int rt)
  118. {
  119. if(T[x].le == le && T[x].rt == rt)
  120. return T[x].num ;
  121. int Mid = (T[x].le + T[x].rt)>>1 ;
  122. push_down(x) ;
  123. if(le > Mid) return Query(R(x) ,le ,rt) ;
  124. else if(rt <= Mid) return Query(L(x) ,le ,rt) ;
  125. else
  126. {
  127. int mx = 0 ;
  128. if(T[L(x)].rc == T[R(x)].lc)
  129. mx = -1 ;
  130. return Query(L(x) ,le ,Mid) + Query(R(x) ,Mid+1 ,rt) + mx ;
  131. }
  132. push_up(x) ;
  133. }
  134. int Querynode(int x ,int pos)
  135. {
  136. if(T[x].le == T[x].rt)
  137. return T[x].lc ;
  138. int Mid = (T[x].le + T[x].rt)>>1 ;
  139. push_down(x) ;
  140. if(pos <= Mid)
  141. return Querynode(L(x) ,pos) ;
  142. else return Querynode(R(x) ,pos) ;
  143. push_up(x) ;
  144. }
  145. void LCAC(int u ,int v ,int w)
  146. {
  147. while(top[u] != top[v])
  148. {
  149. if(dep[top[u]] < dep[top[v]])
  150. swap(u ,v) ;
  151. update(1 ,ti[top[u]] ,ti[u] ,w) ;
  152. u = father[top[u]] ;
  153. }
  154. if(dep[u] > dep[v])
  155. swap(u ,v) ;
  156. update(1 ,ti[u] ,ti[v] ,w) ;
  157. }
  158. int LCAQ(int u ,int v)
  159. {
  160. int ans = 0 ;
  161. while(top[u] != top[v])
  162. {
  163. if(dep[top[u]] < dep[top[v]])
  164. swap(u ,v) ;
  165. ans += Query(1 ,ti[top[u]] ,ti[u]) ;
  166. if(Querynode(1 ,ti[top[u]]) == Querynode(1 ,ti[father[top[u]]]))
  167. ans-- ;
  168. u = father[top[u]] ;
  169. }
  170. if(dep[u] > dep[v])
  171. swap(u ,v) ;
  172. ans += Query(1 ,ti[u] ,ti[v]) ;
  173. return ans ;
  174. }
  175. int main()
  176. {
  177. while(~scanf("%d%d" ,&n ,&m))
  178. {
  179. int u ,v ,w ;
  180. num = 0 ;
  181. memset(head ,-1 ,sizeof(head)) ;
  182. for(int i = 1 ;i <= n ; ++i)
  183. scanf("%d" ,&g[i]) ;
  184. for(int i = 1 ;i < n ; ++i)
  185. {
  186. scanf("%d%d" ,&u ,&v) ;
  187. addedge(u ,v) ;
  188. }
  189. dep[1] = siz[0] = 0 ;
  190. dfs_find(1 ,1) ;
  191. idx = 1 ;
  192. dfs_time(1 ,1) ;
  193. build(1 ,1 ,n) ;
  194. for(int i = 1 ;i <= n ; ++i)
  195. update(1 ,ti[i] ,ti[i] ,g[i]) ;
  196. char s[5] ;
  197. for(int i = 0 ;i < m ; ++i)
  198. {
  199. scanf("%s" ,s) ;
  200. scanf("%d%d" ,&u ,&v) ;
  201. if(s[0] == 'C')
  202. {
  203. scanf("%d" ,&w) ;
  204. LCAC(u ,v ,w) ;
  205. }
  206. else if(s[0] == 'Q')
  207. printf("%d\n" ,LCAQ(u ,v)) ;
  208. }
  209. }
  210. return 0 ;
  211. }


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

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

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

评论(0

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

全部回复

上滑加载中

设置昵称

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

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

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