[GYM102994K] Data Structure

又是一道能证明我是数据结构飞舞的题呢。

题目链接。

题意

给定一棵 个点的树， 为根，初始所有点点权为 。

现在有 次操作，操作分为两种。

第一种是修改操作，给定 ，需要给点 子树内，所有和 之间距离 的点，点权增加 。

第二种操作是给定一个点，查询这个点现在的点权。

， 组数据，时限 秒。

题解

感觉是一眼根号分治，但是感觉难点在后面。

对于 的操作：

考虑此时被影响到的深度，最多只有 种。

那么薅出整棵树的 bfs 序。

对于一个点 ，与一个数字 ，可以发现所有 子树内，与点 距离为 的点是一个区间。

这个性质是非常好的，说明此时的操作在 bfs 序上是至多 个区间。

那么找到这些区间后，来一个 的分块维护就能解决这种情况。

那么如何找到这些区间呢，考虑建一个新的森林出来。

点 的父亲 满足：

1. ；
2. 且 最小。

人话就是说，如果 有儿子，那么 的父亲就是他的第一个儿子。

否则， 和自己同层的右边的点，是一个父亲。

可以发现，这样从一个点 ，往上跳 步，跳到的就是 在原树上往下 层的最左侧点。

当然此时有可能跳到子树外面，所以还需要额外判一下。

所以直接对这棵树树剖，只需要 就能找到一次操作的所有左端点。

这样找到了左侧点，同样方法找一下右侧点即可。

对于 的操作：

暴力一点，直接对所有 分开讨论！

对于每一种 分开求出 dfs 序，然后使用 的分块维护。

找到区间也是直接在上面那棵树上跳一跳就好了。

dfs 常数很大，可能需要改成递归形式。

复杂度 。

为啥我常数这么大啊日

QOJ 的提交记录。