求今天传智杯 F 的正解

学术版

vegetaBle_king @ 2021-12-19 22:07:33

RT，其他的都在赛时 A 了

by SUNCHAOYI @ 2021-12-19 22:23:19

我用 \texttt{LCA} 过了。

by Loser_King @ 2021-12-19 22:24:22

考虑离线查询后按深度从大到小对结点操作，对于每个深度记录需要用到它的结点。把节点按 dfn 序重排后就变成了两种操作：对于当前深度的结点做后缀和和对子树的区间查询。用树状数组维护即可

by Loser_King @ 2021-12-19 22:28:55

有点不太清楚：是“对于当前深度的结点做后缀加一和对子树 indfn~outdfn 的区间查询”

by vegetaBle_king @ 2021-12-20 19:59:30

@Loser_King 懂了，thx