CF757G Can Bash Save the Day?

发表于 分类于 ， ， 阅读次数：

题意：给出一棵 个节点的树，边有边权，再给出一个排列 ，支持：

  • 给出 ，求

  • 交换

强制在线，，时限 。

套路题。

将问题转化为：

  • 点亮一个点
  • 查询 到已经点亮的点的距离之和

按 的顺序点亮点，然后将这个数据结构可持久化，即可快速提取前缀 对应的版本，从而快速查询 ，两次查询即可拼出答案。

对于相邻交换，只有前缀集合 发生了变化，对该版本进行单点修改即可。

现在考虑如何解决转化后的问题。

先将树三度化（添加长度为 的边，没啥细节），再建立可持久化边分树。（可持久化点分树是行不通的，难以管理多个儿子）

边分树上要记录区域内现有点数和、深度和。查询的时候贡献是“查询点深度x对面点的个数+对面的深度和”。每次点亮会修改 个分治区域（即边分树节点）。

时空复杂度都是 。