省选完了直接回去 whk 了，后面逐渐忘了这场比赛，现在校内重做才来改题。
D1T1
题意：编写一个简化版的 C++ 预处理器，只需要等量全字替换即可，不能无限展开。
大模拟。注意读入的时候先读一整行再说，比较麻烦。
D1T2
题意：给定一棵大小为 $n$ 的树，每个点权值必须在给定区间 $[l_i, r_i]$ 中间。你需要找一条链，并对这条链每个点填上合适的权值使得这条链上最大值和最小值之差不超过 $K$。问有多少种填法，并求出所有填法的权值和。$n\leq 200$，$1\leq l_i \leq r_i\leq 10 ^ 9$，$1\leq K\leq 10 ^ 9$。
这里只讨论求填法的方法，权值和类似。
首先考虑一种 $O(na)$ 的做法。考虑简单的容斥，首先定义一段权值区间的 $v(l, r)$ 为任意找一条链并且填入的权值 $\in [l, r]$ 的方案数。那么我们可以把答案写作：$ans = \sum _{r - l = k} v(l, r) - \sum _{r - l = k - 1} v(l, r)$。这个转化为了我们只需要求 $O(a)$ 个区间的 $v(l, r)$。由于确定权值区间之后，每一个点填的方案数是确定的，于是我们可以考虑直接树形 DP，可以做到 $O(n)$ 求一段区间的 $v(l, r)$。于是总复杂度就是 $O(na)$ 的。
考虑如何甩掉这个 $a$。注意到由于 $r - l$ 不变（对 $k$ 和 $k - 1$ 分别求），我们平移的时候如果 $l, r$ 都没有碰到任何一个 $l_i / r_i$，那么每个点的贡献其实是一个常数或者一个一次函数。那么只要没有碰到，整个问题的答案就是一个 $n$ 次多项式，加上问前缀和，就是 $n + 1$ 次多项式。所以如果这个长度比较长，我们可以询问 $O(n)$ 个区间的答案，然后插值得到这段的答案。
总复杂度 $O(n ^ 3)$，常数比较大，可能需要卡常。代码见 https://uoj.ac/submission/596401。
D1T3
到这里看。
D2T1
题意：给定 $n$ 个数 $c_i$，$m$ 次询问，每次给出 $cnt_i$ 质数 $p_j$，问有多少种选择数的方案使得这些数的乘积能被所有给出的质数整除，对 998244353 取模。$c_i, p_j\leq 2000$，$n\leq 10 ^ 6$，$m\leq 1500$，$\sum cnt_i\leq 18000$。
令值域为 $a$。
首先考虑由于 $>\sqrt a$ 的质数每个数只会有一个，所以我们可以按照大质数分类，每一类中间都至少选一个。
我们可以考虑 DP，记当前 $f(s)$ 表示小质数的状态为 $s$ 的方案数，然后不存在大质数的可以直接加入进去 DP，对于每个大质数，将他的倍数全部拿出来，容易发现这些数中间至少选一个，可以先不考虑至少选一个把所有加进去，最后在 $f’(s)$ 减去 $f(s)$。
记 $\pi(x)$ 表示 $x$ 以内的质数个数，这样的复杂度是 $O(2 ^ {\pi (\sqrt a)} am)$，如果我们预处理的话写起来比较麻烦，当然这样的复杂度也足以通过 85pts，如果要通过的话可能需要卡常，代码见 https://loj.ac/s/1446854。
我们可以考虑容斥，现在相当于对于小质数集合的每一个子集，都需要计算不包含这些小质数（剩下的小质数随意）并且需要包含所有给出的大质数。假设容斥集合为 $t$，相当于是小质数状态需要在 $s = U\oplus t$ 里，我们可以预处理 $f_{p, s}$ 表示大质数是 $p$ 并且小质数状态是 $s$ 子集的个数，对于每一个大质数，$f_{p, s}$ 中间至少选一个，剩下没有大质数限制并且小质数状态在 $s$ 里面的随便选。对于每一个 $t$ 都只需要枚举每个大质数，$f_{p, s}$ 用高维前缀和预处理一下即可，总复杂度 $O(2 ^ {\pi (\sqrt a)} \sum cnt_i + \pi(a)\pi (\sqrt a) 2 ^ {\pi(\sqrt a)})$，可以通过。代码见 https://loj.ac/s/1659582。
D2T2
到这里看。
D2T3
题意：有一棵 $n$ 个点的二叉树（每个点有不超过两个儿子），每个点有一个点权 $a_i$，每次可以切断一条边，切断的时候两边会交换点权，代价加上两边点权和。问将所有边切断的最小代价。$n\leq 5000$，$1\leq a_i\leq 10 ^ 9$。
容易发现对于一棵子树只有外部的一个点会进来参与交换，也只有一个点会被交换出去，那么我们就可以直接设计 DP 状态。记 $f(x, u, i)$ 表示在 $x$ 的子树内部，最后 $u$ 出去交换，交换进来的点会交换 $i$ 次的最小代价。注意我们只计算内部的点在子树内部的交换的代价。
转移的时候如果有两个儿子，就有 6 种转移方式，当然可以钦定左右的交换顺序，这样就只有 3 种了。记 $fl$ 表示左边的 DP 数组，$fr$ 表示右边的 DP 数组，$f$ 表示父亲的 DP 数组，用 $\to$ 表示 chkmin 操作，大力转移可以得到：
直接转移可以根据树形背包的复杂度分析，得到 $O(n ^ 4)$，可以通过 28pts。
注意到上面的转移都可以拆分成独立的形式，这样的话我们实际只需要多枚举几次 2 维的转移即可。这样的话复杂度和状态数等同，都是 $O(n ^ 3)$，卡一下空间可以通过 64pts。代码见 https://loj.ac/s/1659587。
现在我们关键是优化状态数，当前的状态数是 $O(\sum sz_x deg_x)$ 的。注意到假设 $u$ 是左儿子的节点，那么对应的 $i$ 一定不超过右儿子的深度，那么我们就可以认为这个状态数也是树上背包的复杂度，这样状态数就降为了 $O(n ^ 2)$，同时复杂度也降为了 $O(n ^ 2)$，可以通过。
实现的时候对于每一个 $f(x, u, *)$ 开一个 std::vector 就好了。写起来非常麻烦，由于 $u$ 是用 dfn 表示的，容易写错。代码见 https://loj.ac/s/1659692。