题解

思路

所有做法都基于递推 $f(x,y)=a_xa_y+f(p_x,p_y)$。数据规模逐步放宽后，分别利用链上同层点唯一、直接递推以及按层宽度记忆化来加速。

做法

子任务一：链

树是一条链时，同一深度只有一个点，所以询问一定满足 $x=y$。预处理根到每个点的权值平方和即可 $O(1)$ 回答。

子任务二：直接上跳

对每个询问让两个点同步跳向父亲，并累加当前权值乘积。单次复杂度为树高，因而总复杂度 $O(qn)$，适用于 $n,q\le 2000$。

满分做法：按层宽度记忆化

记深度 $d$ 的点数为 $c_d$。一次尚未被记忆化的状态 $(x,y)$ 会转移到唯一状态 $(p_x,p_y)$。

若 $c_d\le B$，则这一层最多只有 $c_d(c_d+1)/2$ 个无序点对，可以记忆化所有实际访问的状态。若 $c_d>B$，一次询问在该层最多访问一个状态，而这样的“宽层”总数不超过 $n/B$。因此，每个询问在宽层上花费 $O(n/B)$，窄层状态在整个运行过程中至多被计算 $O(nB)$ 次。

取 $B=320$，使用迭代方式从当前点对向上找到首个已有答案，再倒序回填。因为 $f(x,y)=f(y,x)$，只存三角矩阵，最坏空间约为 $n(B+1)/2$ 个 64 位整数。

正确性说明

每个状态都严格按照定义满足

直接上跳逐项累加该式。满分算法只是把已经算出的窄层状态保存并复用；回填时仍逐层应用同一递推，所以不会改变答案。链算法是 $x=y$ 时该递推的前缀平方和特例。

复杂度

取 $B=320$，满分算法总时间为 $O(nB+qn/B)$，空间为 $O(nB)$；链算法为 $O(n+q)$，直接上跳为 $O(qn)$。