今天讲课,不打比赛!
点名!
DSU!平衡树!树上割点!
1.DSU
大概思路是将树上节点%最大%的子节点(称之为重节点)之外的所有节点合并到重节点,计算完成后再把其它节点加回原树就行了。
(重节点:子节点和子节点的子节点和……的数量)
有啥用呢?答:没啥用可以防止更新值时影响其它子节点
2.树上割点
基于DSU找重节点的方法,遍历子节点,优先遍历重节点并储存在数组中
优点:将树存在数组中,更好修改和维护
缺点:难,我不会用
3.平衡树
两部分
1.二叉搜索树
2.堆(priority)
我不会