A

贪心填。先尽量填竖着的再填横着的。因为这样最多会浪费 $1$ 个，所以达到了答案的上界。求出上界判断是否 $\leq$ 即可。

B

枚举一个位置 $i$，前面只保留 $0$ 后面只保留 $1$，判断是否合法即可。

C

首先第一步横着走还是竖着走都是一样的。我们设第一步横着走。

那么横着走只可能用奇数位置的 $c_i$，竖着走只可能用偶数位置的 $c_i$。枚举总共有几段，然后贪心选择最小的即可。注意要保证每个 $c_i$ 被至少选一次。

D

推一下式子：设 $g=\gcd(a,b)$：

$$ c\frac{ab}{g}-dg = x\\ cab = gx + dg^2\\ $$

设 $a' = \frac{a}{g},b' = \frac{b}{g}$：

$$ ca'b' = \frac{x}{g}+d\\ a'b' = \frac{\frac{x}{g}+d}{c} $$

我们枚举 $g|x$，相当于问有多少对数字 $(a',b')$，满足 $\gcd(a',b')=1$ 并且 $a'b' = x$，设 $x$ 有 $w(x)$ 个质因子，答案就是 $2^{w(x)}$。线性筛预处理 $w(x)$ 即可。复杂度 $O(n+\sqrt n)$ ，可能需要卡常。

E

暴力做法：枚举 $l_1,r_1$，然后以这个为开头整一个 dp：设 $f_{i,j,c}$ 表示当前考虑到位置 $s_i,t_j$ 了（这两个位置还没选），最后一次选的字符是 $c$，转移枚举下一步选哪个即可。复杂度 $O(n^4 |\Sigma|)$。

复杂度瓶颈在于枚举 $l_1,r_1$，考虑把枚举这个的过程也扔到 dp 里：设 $f_{i,j,c,0/1}$ 表示考虑到位置 $s_i,t_j$，如果最后一维是 $0$，$c \in \{0,1\}$，表示当前是在枚举 $i$ 还是枚举 $j$（这里设计成先移动 $i$ 再移动 $j$ 是为了防止算枚举的方案数）；如果最后一维是 $1$ 表示当前已经选好了某个位置，$c$ 就是正常表示最后一个字母是啥了。最后枚举结束的位置把答案加起来即可。

写下转移式子：对于第一种转移，有：

$$ \begin{align*} f_{i,j,0,0} &\to f_{i+1,j,0,0}\\ f_{i,j,0,0} &\to f_{i,j,1,0}\\ f_{i,j,1,0} &\to f_{i,j+1,1,0}\\ f_{i,j,1,0} &\to f_{i+1,j,s[i],1}\\ f_{i,j,1,0} &\to f_{i,j+1,t[j],1} \end{align*} $$

对于第二种转移，就是暴力时的转移式子，也就是：

$$ \begin{align*} [c \neq s[i]]f_{i,j,c,1} &\to f_{i+1,j,s[i],1}\\ [c \neq t[j]]f_{i,j,c,1} &\to f_{i,j+1,t[j],1} \end{align*} $$

不过注意到我们这样实际上只要某一个串开始选就会被计入答案了，也就是说我们会多算某一个字符串选空字符串的情况，最后减去即可。这里减去要枚举每一个区间，判断是否可行，然后减去能产生的贡献。复杂度 $O(n^2 |\Sigma|)$。空间需要稍微注意一下。

F

普及组树形 dp。考虑树形 dp 求直径我们会记录 $v$ 往下的最长单链的长度，这个题我们也这样搞：设 $f_{v,i}$ 表示 $v$ 子树，最长单链长度为 $i$ 的方案树，转移合并两个子树，枚举是否切割，如果不切的话， $f_{v,i} \times f_{x,j} \to f_{v,\max(i,j+1)}$，这里要求 $i+j+1 \leq k$ 即可。树形背包，两维只需要枚举到 $sz_v,sz_x$。复杂度 $O(n^2)$。

转移（或许？）可以长链剖分优化，因为第二维只关于深度，转移整体平移一下，所以可以直接 $O(1)$ 继承长儿子，剩下的暴力合并打标记即可。

G

如果不需要修改，答案就是 $\sum_{v \in V} (\text{deg}(v) \bmod 2)$：因为我们可以构造欧拉回路，将奇点都连到一个工具点 $S$ 上，然后跑 $S$ 开始的欧拉回路，按照方向是入边还是出边来分配颜色就好了。

考虑如何动态维护这个东西：一个直观的想法是根据两端点的度数奇偶性进行分类讨论，但是我们新加入的边某个端点是奇点的时候我们要依据这个端点多余的边来确定新的点的颜色，所以我们记录 $to_x$ 表示如果 $x$ 是奇点，那么 $x$ 没配对的边是哪一个；

考虑现在加入边 $w=(u,v)$：

• 如果两个端点都是偶点：那这个边给什么颜色都无所谓，不失一般性我们设这个边的颜色为 $0$；
• 如果一个端点是奇点一个是偶点：设 $u$ 是奇点，那么 $w$ 的颜色和 $to_u$ 的应该相反，然后 $u$ 变成了偶点，$v$ 变成了奇点，所以还有 $to_v = w$；
• 两个端点都是奇点：我们假设 $u$ 和 $v$ 不在一个联通块：首先先把 $w$ 加入 $u$ 中，发现 $w$ 的颜色和 $to_u$ 的应该相反；然后把 $w$ 加入 $v$ 中：发现这时候 $w$ 的颜色和 $to_v$ 应该相反，也就是 $to_u$ 和 $to_v$ 颜色应该相同；但是有可能不相同，解决方案是我们考虑一个联通块内反转所有颜色的边答案是不变的，所以我们把 $v$ 的联通块所有的边颜色反转即可。

为了支持这些操作，我们要写一个并查集维护在同一联通块的边，每个集合维护一下 $0$ 边的哈希值和和 $1$ 边的哈希值和。支持某个集合反转可以用类似带权并查集的方法：我们让某个点 $v$ 的权值为 $v$ 到并查集根的所有点的颜色的异或，然后我们钦定并查集根的颜色为 $0$，就能支持反转了。复杂度 $O(n \alpha(n))$。注意小心维护全局答案和每个联通块的值的答案。

注意细节：第三种类如果 $u,v$ 在一个连通块内不能进行反转，要不然会违反根颜色钦定为 $0$ 的性质。