0315 测试
T1
首先它可以四维偏序，但是难写难调常数还丑陋无比。
观察到三维的乘积不是很大，考虑对维度的乘积下手，把最小的那一维拿出来暴力，剩下的是三维偏序，是 $O(n^\frac{4}{3}\log^2 n)$ 的，还是比较难写，也比较难过。
于是干脆把最小的两维拿出来暴力，这样就是二维偏序了，可以 set，复杂度 $O(n^\frac{5}{3}\log n+n\log n)$，感觉复杂度不太平衡，考虑给查询平衡一下复杂度，对于第三维分类讨论，如果最长的一维超过 $O(n^\frac{2}{3})$，那么用 set，否则添加的时候在最长的一维的每一层暴力维护该层往上和往下遇到的第一个点的位置。
总复杂度 $O(n^\frac{5}{3}+n^\frac{4}{3}\log n)$，好写，常数小。
其实还有更聪明的暴力，每 $\sqrt q$ 次询问 BFS 一遍重构答案，然后其它的暴力。
能根号重构的前提条件是会做修改全在查询前面的情况。
T2
首先想到可以暴力 AC 自动机，但是这样的复杂度是 $O(nqm\sum)$ 的，大概是 $1.3\times 10^{10}$，过不了。
然后想到 $m$ 比较小，可以考虑用矩阵乘法优化，查询可以树链剖分一样搞，复杂度是 $O(nm^3+q\log^2nm^2)$ 的，理论上是 $10^9$ 级别的，还是过不了，实际上由于第二个查询的 $\log n$ 很小，是可以过的。
也考虑类并查集的方式，将询问放到 $lca$ 上，在 $lca$ 处并查集做合并，复杂度 $O(n\alpha(n)m^3+qm^2)$，实际上常数丑陋，无法通过。
事实上不带修的树剖可以做到 $O(q\log nm^2)$，直接在 $dfn$ 上开一维的数组维护 $top$ 到自身的前缀和即可，这个做法常数较大，过不了。
- 对有向链树剖时要注意顺序，具体的，线段树存储的是自顶向下的。跳树剖的时候是自底向上的。因此，对于 $u$ 到 $lca$ 的部分，应该查线段树的反向信息，并将单次查询的结果翻转后拼接起来。对于 $lca$ 到 $v$ 的部分，应该查线段树的正向信息，将单次查询的结果翻转后拼接起来最后翻转整个序列。
T3
可以树形 DP，然后发现好像一个点的转移复杂度只和它下面最浅的叶子的深度有关，好像可以类似长链剖分的做。
有一个问题是长链的转移比较不对劲，没法快速做。但是又因为复杂度是和最浅的叶子的深度有关，于是可以把链单独拿出来做转移。
对于有多个儿子的点暴力转移，对于只有一个儿子的一段链，可以算出这一段链的长度在链顶 NTT。
复杂度是有保证的，有多个儿子的转移，复杂度同长链剖分，单个儿子只会在链顶转移，而又因为每个点至多对 NTT 贡献 $\log$ 次每 NTT一次就会合并一次（注意到是较短链贡献一遍），所在子树大小翻倍，因此很容易证明其复杂度是低于 $O(n\log^2n)$ 的。
实际上上界是 $O(n\log n)$，因为合并两条单链的时候只有较短的那条单链贡献。
- 封装 NTT 的时候不要左移两遍，具体的，设置
multi函数 $lim$ 参数的时候不要把 $lim$ 设成 $1<<\log_2(n)+1$，而应该设成 $\log_2(n)+1$。