选择性记录

想法还是比较接近的。注意到 $n$ 很小，考虑枚举集合 $S$ 作为最大前缀和的排列数，那么这个排列应该有两个特点：

对于 $1 \leq i \leq |S|$，所有后缀和都 $\geq 0$；对于所有 $|S|+1 \leq i \leq n$，所有前缀和 $<0$。

考虑把两个特点分开处理，令 $f_i$ 表示选定集合为 $i$，满足第一个特点的方案数，$g_i$ 表示满足第二个特点的方案数。转移是平凡的，时间复杂度 $\text{O}(n2^n)$。

不妨假设 $a \leq b \leq c$，那么就有 $a \leq \frac{1}{3}n,b \leq \frac{1}{2}n$。我们考虑去选出大小为 $a,b$ 的连通块，一定不劣。

先考虑树的情况，考虑以重心为根，那么对于 $a$ 的连通块一定不经过根，即有解的条件为：存在大小超过 $\frac{n}{3}$ 的子树。

然后考虑扩展到图的情况，横叉边会将生成树中的若干个子树连接，考虑找到这样的 $siz \geq a$ 的连通块，此时可以说明有解，在这个过程中，该连通块一旦存在大小 $\leq 2a$，剩余部分 $\geq n-2a$，由于 $n=a+b+c$，那么有 $n-2a=b+c-a \geq b$，故有解。