Luogu6778 [Ynoi2009] rpdq

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

题意：给定一棵 个点的树，边有边权。

每次询问给出 ，求：

答案对 取模。

允许离线， ，时限 ，空限 。

本题解无 树分块，请放心食用。（迫真）

使用二次离线莫队。

容易将问题转化为 次

的求解。

难点在于 ，这是 “经典问题”，将点 到根的点权加上父边边权，然后查询 到根的路径和即可得到。

问题转化为 次路径加与 次路径求和。

然后我们尴尬地发现，常用的树上数据结构几乎全部带 ，不能很好地平衡复杂度。

考虑树分块。

每个点只归属于一个块，每个块形成一个树上联通块。记块中的最浅点为关键点。

接下来是分块方法。

若 且 ，则将 的子树分成一块。（第一类）

这样还剩了所有子树大小 的点没有归属，这些点构成一棵分叉为 的树。

对于每条不分叉的链条，尽量按照 划分，如果最后剩下一小段不足 ，也直接分成一块。（第二类）

第二类块的个数为 ，形态为一条链。

第一类块的个数不限，形态为一棵子树。一类块下面不再有块，一类块上面一定是二类块。

记 为 的父亲， 为 所在块的关键点。

  • 对 进行链加

    记 表示 到关键点的路径的和。

    若 在一类块中，暴力 整块更新 ，然后修改 ，则转化为 在二类块中的情况。

    若 在二类块中，仍然先暴力 整块更新 。

    还会对祖先块的 进行贡献。注意到由于二类块形态是一条链，一定是整个块都加，只需要记下整块标记。

    对于二类块的关键点，维护到根的路径的和，由于二类块的个数较少，可以每次修改后暴力 计算。

  • 对 进行链查询

    若 在一类块中，答案加上 ，然后查询 ，则转化为 在二类块中的情况。

    若 在二类块中，答案为

    其中 表示块 被整体加的次数， 表示 到关键点的距离， 表示关键点 到根的路径和。

时间复杂度 ，空间复杂度 。