SPOJ QTREE 系列简要题解
QTREE1 把 $(fa_i,i)$ 的边权作为 $i$ 的点权，然后就是个树剖板子了... 但是注意查询时 LCA 是不能查的，需要判一下。 而且这题竟然不能交 C++ ，然后我改了半个小时才把 C++ 改成 C QAQ QTREE2 DIST 操作只需要维护树上前缀和即可求出答案。 KTH 操作大力讨论一下答案应该在 $u-lca$ 的链上还是 $v-lca$ 的链上，然后倍增上去即...
QTREE1 把 $(fa_i,i)$ 的边权作为 $i$ 的点权，然后就是个树剖板子了... 但是注意查询时 LCA 是不能查的，需要判一下。 而且这题竟然不能交 C++ ，然后我改了半个小时才把 C++ 改成 C QAQ QTREE2 DIST 操作只需要维护树上前缀和即可求出答案。 KTH 操作大力讨论一下答案应该在 $u-lca$ 的链上还是 $v-lca$ 的链上，然后倍增上去即...