Description：

---

设深度为 k的满二叉树的\(\mathrm{Pr\ddot{u}fer}\)编码序列为\(P=\{p_i\}\)

\(m\)次询问，对于每次询问给出 a d m，求\(\sum\limits_{i=0}^{m-1}p_{a+i\times d}\)

\(2\leq k \leq 30 , 1 \leq q \leq 300\)

Examples:

---

input1	output1
3 5 1 1 1 2 1 1 3 1 1 4 1 1 5 1 1	2 2 1 3 3
input2	output2
4 4 2 1 5 4 4 3 4 8 1 10 3 2	18 15 5 13
input3	output3
7 1 1 1 125	4031

Solution：

---

太神了！

考虑暴力搜索，搜索状态为 search(x, k)，表示以\(x\)为根深度为\(k\)的子树的\(\mathrm{Pr\ddot{u}fer}\)编码中对答案的贡献。为了方便顺便维护两个值 i m分别表示在删除这个子树之前已经删了多少个点，在这棵子树的\(\mathrm{Pr\ddot{u}fer}\)编码中有多少点属于等差数列。

这样 search(x, k)可以递归到 search(2 * x, k - 1), search(2 * x + 1, k - 1)，还要考虑下根节点是否属于等差数列，并且根节点，左子树，右子树的删除顺序和根节点是否有父边也有关系，需要处理一下。

但是这样复杂度会是\(\mathcal{O}(2^k)\)，需要优化。

然后很神的就是将搜索状态设为 solve(k, i, m, hasfa)， hasfa表示根节点是否有父边， ret表示根节点为\(x\)，深度为\(k\)的满二叉树，之前已有\(i\)位\(\mathrm{Pr\ddot{u}fer}\)编码，子树的编码中接下来还有\(m\)个所需的位的答案为\(ret.a\times x+ret.b+c\times \left \lfloor \frac{x}{2} \right \rfloor \)，这样统计答案的好处在于答案的值是关于根节点的函数，答案的值只与所需点的相对位置有关，而与根节点无关。在不影响左右子树答案的合并的前提下，有利于之后的记忆化搜索。

设当前节点(根节点为x)目前答案为\(ret.a, ret.b, ret.c\)左子树(根节点为2x+1)答案为\(son.a, son.b, son.c\)，根据定义合并后\(\begin{split}ans&=ret.a\times x+ret.b+ret.c\times \left \lfloor \frac{x}{2} \right \rfloor + son.a\times (2x)+son.b+son.c\times \left \lfloor \frac{2x}{2} \right \rfloor \\&=(ret.a+2\times son.a+son.c)\times x+(ret.b+son.b)+ret.c\times \left \lfloor \frac{x}{2} \right \rfloor\end{split}\)

右子树同理。

接下来则是记忆化需要记录的状态，首先，只有当该子树对应的编码区间属于\([a,a+(m-1)\times d]\)，且该子树有父边才进行记忆化。于是，记录的状态为 g[k][i], 表示根节点有父边，根节点为\(x\)，深度为\(k\)的满二叉树，且任意\(p’_{i+j*d}\)均为所需点的答案为\(g[k][i].a\times x+g[k][i].b+g[k][i].c \times \left \lfloor \frac{x}{2} \right \rfloor (P’=\{p’_i\}为该子树的编码序列)\)，因为所有有父边深度为\(k\)的满二叉树删除顺序是一定的，每次询问\(d\)又是固定的，所以选取的相对位置的集合（即答案）只与该子树编码中第一个被选取的点的 offset有关。

为了保证复杂度，只记录\(k\leq 15\)的状态。状态总数最多为\(15 \times (2^{15}-1)\)

然后考虑每次搜索时间复杂度，

1. 当\(15<k\leq 30\)， 最多只会搜索\(2^{15}\)次
2. 当\(1\leq k \leq 15\)，不能记忆化的区间只有\(\mathcal{O}(k)\)个，没有父边的区间最多也只有\(\mathcal{O}(k)\)个

所以单次询问复杂度为\(\mathcal{O}(2^{\frac{k}{2}})\)

Code：

---