保存帖子
发现
索引
热门
陶片放逐
关于
警示后人
板块
P4332 [SHOI2014] 三叉神经树
楼主
huangkx
当前回复
1
已保存回复
1
发布时间
2023/8/21 16:15
上次更新
2023/11/3 02:12:54
查看原帖
更新帖子
被骇客
银
狼
阻止的越权访问
保存失败
警示后人
huangkx
楼主
2023/8/21 16:15
如果您用的是 LCT 写法:
“外界输入”可以不当成结点。
一开始连边时可以全部都连虚边。
要先用 DFS 或其他方法求出每个结点的 val。注意在此过程中并不满足父结点编号小于子结点。(参考第一篇题解)。
在 Splay 上二分时要先考虑右子树,再考虑当前结点,最后考虑左子树。
在 Splay 上二分时要注意判断当前结点时看 val[x](它自己的为 1 的子结点的个数) 而不是 f[x](它的子树中是不是全部都是 val 为 1 的结点)。(不过应该只有我会犯这种错)。
2023/8/21 16:15
加载中...