A - 灾难
题意：给定一个 DAG，求每个点能支配的点的数量。
\(n \le 65534\)，输入的文件大小不超过 1 MB
求一个点支配别人的数量很难求，考虑求出每个点会被那些点所支配。
对于一个点 \(i\) 而言，连向它的点记为 \(p_{i,j}\)，那么能支配 \(i\) 的点必须在 \(LCA_{j=1}^{|p_i|}p_{i,j}\) 到根节点的点上。（这里的 LCA 并不是正常 LCA，我感觉而是类似于另外一颗由这个 DAG 所构成的树的 LCA）.
具体做法如下：对于每个点，求出连向它的点在另一颗树上的 LCA，最后在把自己与那个 LCA 在另一棵树上连接。最后在用 dfs 求出子树大小就可以了。
B - 字符合并
题意：有一个长度为 \(n\) 的 01 串，你可以每次将相邻的 \(k\) 个字符合并，获得一定价值。
给出所有长度为 \(k\) 的串被合并所获得的价值以及得到的新字符，问把原串缩完能获得的最大价值。
\(n \le 300,k\le8\)
注意到 \(n,k\) 都很小，对于一段区间 \([l,r]\) 而言，由于 \(w_i>0\)，所以区间 \([l,r]\) 最终一定会变成 \((r-l+1) \mod (k-1)\) 的 01 串（特别的，为 mod 后为 \(0\) 实际上是 \(k-1\)）。
考虑区间 dp，设 \(f_{l,r,x}\) 表示对于区间 \([l,r]\)，最终变成 \(x\) 这个状态的方案数，转移考虑枚举分界点最后一位。
看起来可能会超时，但实际上很多无效状态和不可能的情况可以剪枝。
C - 异或
题意：
有一颗以 \(1\) 为根节点的由 \(n\) 个节点组成的树，节点从 \(1\) 至 \(n\) 编号。树上每个节点上都有一个权值 \(v_i\)。现在有 \(q\) 次操作，操作如下：
- \(1~x~z\)：查询节点 \(x\) 的子树中的节点权值与 \(z\) 异或结果的最大值。
- \(2~x~y~z\)：查询节点 \(x\) 到节点 \(y\) 的简单路径上的节点的权值与 \(z\) 异或结果最大值。
\(n,q \le 10^5,v_i,z \le 2^{30}\)
看到这两个查询就非常像树剖啊。
而对于异或，很容易想到 tire。
两者结合，用树剖的线段树套 trie 树。
时间复杂度 \(O(n \log^2 n \log V)\)
但这样可能会 TLE，毕竟 8 亿再加上线段树。
注意到不需要修改，可以考虑用倍增去优化，直接把线段树改成 st 表维护，查询 \(O(\log V)\)。
总时间复杂度 \(O(n\log n \log V)\)
赛后发现用可持久化线段树其实可以做到 \(O(n \log V)\)，其实就是不树剖了，直接就在 dfs 的时候处理，两种情况分别考虑。第一种可以继承上一个 dfn 的状态，第二种则是继承父节点的状态。