风格有点像 NOI2017，有送分题，但是并不很好写（不过似乎比去年 day2 游戏好写？）
今天发挥还不错，争取把分数稳定下来。
Tree
对于操作 1 ，用一个变量记录。
对于操作 2 ，对两点在原树上 $\text{lca}$ 的位置进行讨论。不妨设之为 $\text{lca_0}$ 。
分为以下情况：
- $\text{lca}$ 在新根 $\text{rt}$ 与 $1$ 的路径上
- $\text{lca}$ 在新根的子树里
- $\text{lca}$ 在除了上述之外的地方
对于 $1$ 我们可以用 $\textbf{lca(rt, lca}_0 \textbf{)= lca_o}$ 加以判定 ；
对于 $2$ 可以直接用 $\text{dfs}$ 序判断。
注意：
- 初始根为 $1$
- 注意特判 $\text{rt, lca}_0$ 是否重合
Or
有一个显然的DP就是，如果设状态 $dp[i][j]$ 表示考虑长度为 $i$ 的序列 $B_i$ 含有 $j$ 个 $1$ ，那么就有：
而由 $\sum_{i=1}^n \binom{n}{i} = 2^n$ 这个结论可以立刻知道： 考场写的暴力 NTT 是 $O(nk\lg k)$ 的，可以获得 $59$ 分。
考虑使用指数生成函数： 这可以用类似普通快速幂的倍增方法求出。即： 对于 $n$ 为奇数的情况暴力算一次就好了。
这样递归为什么就可以解决问题呢？$e^{2^i x}-1$ 到哪儿去了？在递归边界 $n = 1$ 里！
时间复杂度为 $O(k \lg n \lg k)$，可以通过。
