【求助】关于动态树问题维护子树信息
  • 板块学术版
  • 楼主2020kanade
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/5/19 13:17
  • 上次更新2023/10/28 01:08:20
查看原帖
【求助】关于动态树问题维护子树信息
456724
2020kanade楼主2022/5/19 13:17

给定一个结点带权的动态森林,支持连接\切断一些边以及点权修改。

如何在线查找以某结点为根的子树权值第k小结点?应当用什么数据结构维护:

这边一开始想的是LCT加平衡树/权值线段树,后来发现死在了维护连通块破坏上。

请问LCT是否可以较为优秀地完成,需要用到什么数据结构/思路?如果LCT不能,哪些维护动态森林的DS可以?

提前谢谢各位

2022/5/19 13:17
加载中...