游戏
每个点 \(u\) 提出最深的子树，次深的子树和次次深的子树，记深度为 \((a_u,b_u,c_u)\)，对于一个询问 \((x,y,z)\) 就是找一个 \(u\) 满足 \(a_u\ge x\) 且 \(b_u\ge y\) 且 \(c_u\ge z\)。第一维排序扫描线，第二维作为树状数组的下标，记录第三维最小值，总复杂度 \(O(n\log n)\)。
马戏团里你最忙
如果 \(K\) 不大，可以直接暴力 \(O(2^nnK)\)。
如果 \(K\) 大，发现答案数组是可以线性递推的，具体的，\(f_{i,s}\) 表示经过 \(i\) 轮 \(s\) 的答案，将 \(f_i\) 看成一个长度为 \(2^K\) 的数组，有 \(f_i=\sum_{j=1}^mf_{i-j}a_{j-1}\)，这个 \(a\) 就是递推式，递推式长度 \(m\) 是 \(O(n)\) 的。有了递推式，可以用线性递推的技巧，\(m^2\log K\) 的预处理，然后 \(O(2^nm)\) 的求 \(f_K\)。
如果不会 BM 找递推式，可以使用高斯消元。
树
如果给定的树是一条链，我们可以用 \(f_{i,j}\) 表示 \([i,i+2^j)\) 的答案，有如下转移：
\[f_{i,j}=f_{i,j-1}+f_{i+2^{j-1},j-1}+\sum_{k=i+2^{j-1}}^{i+2^j-1}2^{j-1}-2^j\times [v_k的第j-1位是1] \]求和部分可以用前缀和维护，时间复杂度 \(O(n\log n)\)。
考虑 \(u\) 子树内距离 \(u\) 为 \(d\) 的点，在 BFS 序上是一个区间，如何表示出子数内距离 \(u\) 不超过 \(d\) 的信息呢？
如图，可以表示为两个点一直往最右孩子走的同层前缀和之差。这张图表示了距离 \(u\) 不超过 \(2\) 的信息——\(u\) 往最右孩子走 \(2\) 步的同层前缀信息减去 \(v\) 往最右孩子走 \(2\) 步的同层前缀信息。如果这个点是叶子，那么最右孩子指向假设这个点有孩子，这个孩子 BFS 序上的前一个点，图中虚线的那条边就是对应叶子指向的点。
于是问题转化为一直往右儿子跳，同层前缀信息之和。这个问题和序列上的问题类似，\(f_{u,i}\) 表示距离 \(u\) 往最右孩子走 \(2^i-1\) 步的前缀信息之和，需要用到的信息都能预处理。总的时间复杂度 \(O(n\log n)\)。
还有其它 \(O(n\log n)\) 的做法，常数可能比较大。
标签：同层,log,信息,最右,ddd,递推,前缀 From： https://www.cnblogs.com/aurora2023/p/17277184.html