社区讨论
关于树链剖分性质的疑惑
学术版参与者 4已保存回复 8
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @mdvd4xdj
- 此快照首次捕获于
- 2025/08/03 15:31 7 个月前
- 此快照最后确认于
- 2025/11/04 03:16 4 个月前
洛谷进阶书(24年9月第一版)上有句讲解是这么说的:
P165
“树上任何一个结点到根的路径上经过的重链条数不会超过轻边条数减去1”
我对这句话不是很理解
重链把树上的所有的结点分成了若干个集合,而轻边连接了这些集合
所以如果把重链都缩成一个点,那么新图形应该也是一棵树
然后所有的轻边构成了这棵新树的所有边
那么原树上任意一点到根的路径都可以转化到T上的一条路径
形式类似于:重链->轻边->重链->轻边->……->重链
那么“所经过的重链条数应该等于过的轻边条数经加1”才合理啊
qwq求解答
回复
共 8 条回复,欢迎继续交流。
正在加载回复...