问一个动态树维护信息的要求的问题
  • 板块学术版
  • 楼主GameFreak
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/11/12 22:31
  • 上次更新2023/11/13 12:28:56
查看原帖
问一个动态树维护信息的要求的问题
673643
GameFreak楼主2023/11/12 22:31

RT,想知道 LCT 能维护哪些类型的信息,以及化边为点的技巧是不是会有局限性。

主要是某道题需要一个查询子树内所有点到根的距离和,并且我想的做法需要加删边和换根,感觉上可以通过维护虚子树答案和大小合并上去。

结果我先发现边变成的点因为无意义答案不对,然后改成了从一个 std::map 里面拿边权来计算,但还是答案不对。

但是我感觉这个东西跟维护虚子树大小差不多 ,所以就不知道为什么不行,想问一下是不是 LCT 维护的信息需要满足什么性质。

2023/11/12 22:31
加载中...