首页 > 其他 > 详细

树链剖分[模板](洛谷 P3384)

时间:2017-12-03 10:48:05      阅读:216      评论:0      收藏:0      [点我收藏+]

洛谷·[模板]树链剖分

写在前面

首先,在学树链剖分之前最好先把 LCA、树形DP、DFS序 这三个知识点学了

如果这三个知识点没掌握好的话,树链剖分难以理解也是当然的。


树链剖分

树链剖分 就是对一棵树分成几条链,把树形变为线性,减少处理难度

概念

  • 重儿子:对于每一个非叶子节点,它的儿子中 儿子数量最多的那一个儿子 为该节点的重儿子
  • 轻儿子:对于每一个非叶子节点,它的儿子中 非重儿子 的剩下所有儿子即为轻儿子
  • 叶子节点没有重儿子也没有轻儿子(因为它没有儿子。。)
  • 重边:连接任意两个重儿子的边叫做重边
  • 轻边:剩下的即为轻边
  • 重链:连接

树链剖分[模板](洛谷 P3384)

原文:http://www.cnblogs.com/chinhhh/p/7965433.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!