关于树链剖分性质的疑惑
  • 板块学术版
  • 楼主_0o0_
  • 当前回复6
  • 已保存回复7
  • 发布时间2025/8/3 15:29
  • 上次更新2025/8/3 20:25:51
查看原帖
关于树链剖分性质的疑惑
671610
_0o0_楼主2025/8/3 15:29

洛谷进阶书(24年9月第一版)上有句讲解是这么说的:

P165

“树上任何一个结点到根的路径上经过的重链条数不会超过轻边条数减去1”

我对这句话不是很理解

重链把树上的所有的结点分成了若干个集合,而轻边连接了这些集合

所以如果把重链都缩成一个点,那么新图形应该也是一棵树

然后所有的轻边构成了这棵新树的所有边

那么原树上任意一点到根的路径都可以转化到T上的一条路径

形式类似于:重链->轻边->重链->轻边->……->重链

那么“所经过的重链条数应该等于过的轻边条数经加1”才合理啊

qwq求解答

2025/8/3 15:29
加载中...