YbtOJ 774「分块算法」奇妙的树
题目链接：YbtOJ #774
小 A 有一棵 $n$ 个点的有根树，以 $1$ 号点为根。$i$ 号点的点权为 $a_i$。
假设 $i$ 号点的父节点为 $f_i$（方便起见认为 $f_1=0$），小 A 发现这棵树非常奇妙，它满足一个特殊的性质：对于任意整数 $i\in[2,n]$，满足 $f_{i-1}\le f_i < i$。
小 A 将会进行 $q$ 次询问，第 $i$ 次询问给出一个区间 $[l_i,r_i]$，求：
$$
(\sum_{x=l_i}^{r_i}\sum_{y=l_i}^{r_i}[l_i\le \operatorname{LCA}(x,y)\le r_i]\cdot a_x\cdot a_y)\mod998244353
$$
强制在线。
$1\le n,q\le2.5\times10^5$，$0\le a_i < 998244353$，$1\le l_i\le r_i\le n$。保证对于任意整数 $i\in[2,n]$，满足 $f_{i-1}\le f_i < i$。
Solution
容易通过归纳证明如下几个性质：
- 性质一：$x$ 的祖先标号必然小于 $x$。
- 性质二：$dep_i$ 随着 $i$ 的增大不降。
- 性质三：设 $g_i$ 为 满足 $f_j < i$ 的最大 $j$，则 $i$ 和 $g_i$ 的深度至多相差 $1$。
- 性质四：标号在 $[l,r]$ 范围内的点构成以 $[l,\min{r,g_l}]$ 中的点为根的若干无交连通子树。
则，对于一个询问 $[l,r]$，如果我们只保留 $[l,r]$ 范围内的点，根据性质四，它将构成以 $[l,\min{r,g_l}]$ 中的点为根的若干无交连通子树。
显然，当且仅当选择的点对 $(x,y)$ 位于同一棵子树中，$\operatorname{LCA}(x,y)$ 会在 $[l,r]$ 范围内。
而要在一棵子树 $T$ 中选择两个点，它们的乘积和为：
$$
\sum_{x\in T}\sum_{y\in T}a_xa_y=(\sum_{x\in T}a_x)(\sum_{y\in T}a_y)=(\sum_{x\in T}a_x)^2
$$
即 $T$ 中所有点权和的平方。
综上，我们要求出的就是仅保留 $[l,r]$ 中的点时， 这些子树点权和的平方和。
据性质一，$[1,l)$ 中的点不可能出现在 $[l,r]$ 中的点的子树里，因此我们实际上可以不用只保留 $[l,r]$ 中的点，而是保留 $[1,r]$ 中的所有点。
于是假设可以离线，把询问按照右端点排序，然后就能把节点一个个加入来扩展右端点了。加入的过程需要更新所有祖先的子树点权和的平方，询问时就是对 $[l,\min{r,g_i}]$ 区间求和。
但这样时间复杂度未免过于浪费，考虑把这个过程分块一下，即每加入 $S$ 个点就重构一次（遍历整棵树统计所有点的子树点权和，并对其平方做前缀和方便区间查询），不满 $S$ 个点根据具体询问，直接求出这个点在谁的子树中更新对应子树点权和并更新答案即可。
至于如何判断一个点 $x$ 在谁的子树中，根据性质三，$[l,\min{r,g_i}]$ 最多只有两种不同的深度，我们求出 $x$ 深度为 $dep_l+1$ 的祖先 $t$（可以使用 $O(n\log n)$ 预处理+$O(1)$ 查询的长链剖分求 $k$ 级祖先算法），如果 $t\le g_i$ 说明 $x$ 在 $t$ 的子树中，否则说明 $x$ 在 $f_t$ 的子树中。
然后发现我们实际上没有必要离线，可以事先预处理出这些信息存下来在线做。
即对于所有 $i=1\sim\lceil\frac nS\rceil$，记录下仅保留标号在 $1\sim (i-1)\times S$ 范围内的点时，所有点的子树点权和 $w_{i,x}$，及其平方的前缀和 $s_{i,x}$。
假设询问的是 $[l,r]$，按照先前的方式，我们在加入 $1\sim (\lceil\frac rS\rceil-1)\times S$ 中的所有点的基础上，枚举 $(\lceil\frac rS\rceil-1)\times S+1\sim r$ 中的点，求出它在谁的子树中更新对应子树点权和并更新答案。
PS: 卡常。本人长链被卡，重链剖分与倍增择选复杂度优的跑然后调了调块长才过。
Code
1 | #pragma GCC optimize("Ofast") |