RT,想知道 LCT 能维护哪些类型的信息,以及化边为点的技巧是不是会有局限性。
主要是某道题需要一个查询子树内所有点到根的距离和,并且我想的做法需要加删边和换根,感觉上可以通过维护虚子树答案和大小合并上去。
结果我先发现边变成的点因为无意义答案不对,然后改成了从一个 std::map 里面拿边权来计算,但还是答案不对。
std::map
但是我感觉这个东西跟维护虚子树大小差不多 ,所以就不知道为什么不行,想问一下是不是 LCT 维护的信息需要满足什么性质。