给定 $n$ 阶树和 $m$ 个操作。每个点 $u$ 维护一个集合 $S(u)$，初始时 $S(u)=\{u\}$。
每次操作选定一条树边 $u\to v$，令 $S(u)=S(v)=\text{\old}(S(u)\cup S(v))$。
对每个 $u$，输出有多少个 $v$ 满足 $u\in S(v)$。
设 $m$ 次操作选择的边为 $e_1,e_2\cdots e_m$。观察 $u\in S(v)$，这等价于序列 $\{e\}$ 中存在某个子序列 $e_{p_1},e_{p_2}\cdots e_{p_k}$ 恰好是连接 $u,v$ 的路径。
如果逆序操作，即序列变为 $e_{p_k},e_{p_{k-1}}\cdots e_{p_1}$，则有 $v\in S(u)$。
于是正序操作 $\sum_{v=1}^n [u\in S(v)]=$ 逆序操作 $\sum_{v=1}^n [v\in S(u)]=$ 逆序操作 $|S(u)|$。
接下来考虑怎样维护 $|S(u)|$。根据容斥定理，有 $|S(u)\cup S(v)|=|S(u)|+|S(v)|-|S(u)\cap S(V)|$。
对 $t\in S(u)\cap S(v)$，由于树形结构约束，必存在子序列 $e_{p_1},e_{p_2}\cdots e_{p_k}$ 代表路径 $k\to \cdots v\to u$ 或 $k\to \cdots u\to v$。
于是不难发现 $|S(u)\cap S(V)|$ 恰好为上次合并 $S(u),S(v)$ 的结果，维护一下即可。时间复杂度 $O(n+m)$。
给定线段树的 $m$ 次区间查询操作，要求构造一棵维护区间 $[1,n]$ 的特殊线段树。
使得查询操作访问结点的次数最少的结点并输出访问结点的次数。
不难得到 $\text{dp}$ 方程
$$ \text{dp}(i,j)=\min(\text{dp}(i,k)+\text{dp}(k+1,j)+w(i,j)) $$
然后考虑依次处理每个询问 $[ql,qr]$ 对 $w(i,j)$ 的贡献。不难发现当 $[i,j]$ 与 $[ql,qr]$ 相交但 $[i,j]\not\subseteq [ql,qr]$ 时询问贡献为 $1$。
问题在于 $[i,j]\subseteq [ql,qr]$ 询问对 $w(i,j)$ 的贡献与询问是否包含 $[i,j]$ 区间的祖结点有关。
有结论任意二叉树的叶子结点数 $=$ 非叶子结点数 $+1$，而线段树恰好为二叉树。
于是不妨转化思路令 $[i,i]\subseteq [ql,qr]$ 得到贡献 $1$，令 $[i,j](i\lt j)\subseteq [ql,qr]$ 得到贡献 $-1$。
于是 $\text{dp}$ 过程中如果划分区间得到 $[i,j]\subseteq [ql,qr]$，则 $[i,j]$ 的子树的总贡献恰好为 $1$。
对应每个询问对 $w(i,j)$ 的贡献，差分维护即可，时间复杂度 $O(n^3+m)$。
给定 $2^k\times 2^k$ 的一个二维 $01$ 串。定义 $B(x,y)$ 表示将二维 $01$ 串循环左移 $x$ 格循环上移 $y$ 格的新二维 $01$ 串。
定义两个二维串之间的异或为对应位置异或。问任意个 $B(x_i,y_i)$ 异或能得到的所有不同的二维 $01$ 串个数。
直接把 $B(x,y)$ 拉成一维，然后高斯消元计算所有 $2^{2k}$ 个 $B(x,y)$ 的秩即可。时间复杂度 $I\left(2^{4k}+\frac {2^{6k}}w\right)$。