QTREE1把 $(fa_i,i)$ 的边权作为 $i$ 的点权,然后就是个树剖板子了...但是注意查询时 LCA 是不能查的,需要判一下。而且这题竟然不能交 C++ ,然后我改了半个小时才把 C++ 改成 C QAQQTREE2DIST 操作只需要维护树上前缀和即可求出答案。KTH 操作大力讨论一下答案应该在 $u-lca$ 的链上还是 $v-lca$ 的链上,然后倍增上去即可求出。所以只...
Luogu分析首先吐槽一句...当初写《幻想乡战略游戏》的时候抄了个错的 ST 表求 LCA 的板子,那题竟然还过了...然后我蒯过来出现各种问题,害我调了好久 QAQ看到这个毒瘤的时限以及修改操作可以想到动态点分治。对于每个节点 $u$ 维护两个堆:一个堆维护点分子树中所有关灯的点到 $u$ 在点分树上父亲的距离,一个维护所有儿子的前一个堆的堆顶。这样子就很好计算每个点的答案了。再维护一个...