A,B 喂猫。
C - Keep Graph Connected
给一张 \(n\) 个点 \(m\) 条边的无向图，边权是 \(1\) 到 \(n\) 中的整数，你现在需要给每个点分配一个 \(1\) 到 \(n\) 中整数的点权，分配完后对于原来的某边如果其连接的两个点恰好有一个点的点权等于边权则其依旧存在，输出一种分配方案使得图依旧联通或判断无解。要求线性。
不难猜想一定有解，考虑任何一棵树，我们直接从某个点 dfs，先给根随便找个点权，现在假设找到某条边，如果这条边的边权等于已经 dfs 到的点的点权，那就把目标节点赋一个不等于边权的点权；反之赋成这条边的边权。一般情况随便找棵 dfs 树就好。
D - AB
给你四个字符 \(C_{AA},C_{AB},C_{BA},C_{BB}\in\{A,B\}\)，你一开始有字符串 AB，你每一次可以选两个相邻的字符，然后把对应的 \(C_{XX}\) 插到这两个字符之间，问你最后可以得到多少不同的长为 \(n\) 的字符串，\(n\leqslant 1000\)。
这里提供一个纯 dp 做法。设 \(f[i]\) 为长度为 \(i\) 的答案，我们发现无论 \(C_{AB}\) 等于什么，最后添加完第一个字符后一边头尾还是 AB，另一边是 AA 或者 BB。为了防止计重，我们强制令我们添加的字符是最后字符串除掉两边中第一个 A 或是最后一个 B（根据 \(C_{AB}\) 而定），为此记辅助数组 \(g(i,0/1,0/1)\) 表示长度为 \(i\)，头尾为 \(0/1\)，是否可以使得中间全部为 A/B，这样转移枚举分界点 \(j\) 即可，复杂度 \(O(n^2)\)，被 \(O(\log n)\) 的分类讨论吊起来打。
E - Random IS
给定长为 \(n\) 的排列 \(a\)，定义在某个局面下（每个数是否被选中）某个位置是好的当且仅当这个位置未被选中，且选中这个位置后，所有被选中的位置的数依旧是单调上升的。如果当前状态还有好的位置，则从所有好的位置中等概率选择一个，反之停止过程，求被选中的位置的个数的期望。\(n\leqslant 2000\)。
我们考虑朴素的 dp，设 \(f(l,r)\) 表示只考虑区间 \([l,r]\) 中的数，目前只选了 \(l,r\) 两个位置，期望还能选多少位置，为了方便设 \(a_0=0,a_{n+1}=n+1\)，则 \(f(0,n+1)\) 即为答案。
考虑转移，我们只需要枚举下一个被选择的好的位置是谁，然后从中间断开即可，设 \(s_1,s_2,\dots,s_k\) 为这个局面所有好的位置，则 \[ \begin{equation} f(l,r)= \begin{cases} 1+\frac{1}{k}\sum f(l,s_i)+f(s_i,r) &k\not=0\\ 0 &k=0 \end{cases} \end{equation} \] 注意到某个位置 \(i\) 是好的当且仅当 \(l<i<r\) 且 \(a_l<a_i<a_r\)，直接枚举可以做到 \(O(n^3)\)。
我们可以用树状数组来优化，具体地把 \(f(l,i)+f(i,r)\) 分别拆开计算，维护左端点/右端点为某个值且右端点/左端点位置上的值小于等于/大于等于某个值的 \(f\) 之和与合法位置个数，复杂度 \(O(n^2\log n)\)。
F - Paint Tree
日常不会套路题。
依旧是关于直径的套路：对于任意一条直径，树上每个点到两个端点距离的较大值等于这个点到每个点距离的最大值。
先拎出来一条直径，处理出每个点到两个端点的距离 \(deep1_i,deep2_i\)。如果直径的两个端点同色，则答案为直径长度，方案数为 \(2^{n-1}\)；如果不是，先假设第一个端点是黑色，第二个端点是白色，到时候方案数乘 \(2\)，把所有不是端点的（点，距离）的二元组按距离从大到小排序（一个点到两个端点的距离都加进去，也就是一共 \(2n-4\) 个二元组）。假设现在的二元组是 \((deep,x)\)，当前还有 \(left\) 个点未被访问到（包含 \(x\)），如果 \(x\) 是第一次被访问到，那么它可以和距离其较远的那个直径端点同色，方案数为 \(2^{left-1}\)，答案为 \(deep\)；如果不是，这时方案数为 \(2^{left}\)（因为 \(x\) 已经在第一次被访问时减掉了），注意到答案不可能比 \(deep\) 更小，因为此时 \(x\) 填什么颜色都会与一个端点颜色相同，所以直接 break。