这篇博客可以公开，就公开了。
A
算法1
$O(2^n)$ 枚举一下每个点染成什么颜色，然后从底向上 确定每一个点的权值， 如果所有点的权值都 $\geq 0$，则这是一组合法解，输出 POSSIBLE 否则继续做。
若没有合法解，则输出 IMPOSSIBLE。
时间复杂度 $O(n \cdot 2^n)$，期望得分 20 分。
算法2
可以考虑用树形 DP 来做。用 $f_{i,j}$ 表示 $i$ 的子树里和 $i$ 颜色不同的点的权值和为 $j$ 可不可行。 从底向上树形 DP 即可。
时间复杂度 $O(nv^3)$，期望得分 40 分。
算法3
因为这部分数据是一条链， 从底向上 dp 用 $f_{i,j}$ 表示是否存在一个合法方案满足上一个与 $i$ 颜色不同的节点是 $j$ 转移的时候， 对于 $i$ 号点 ，枚举上一个和它颜色相同的点 $k$ ，如果 $f_{i+1,k}=\mathsf{true}$ 且 $v_i\geq v_k$，那么这就是一种合法方案。
时间复杂度 $O(n^2)$，期望得分 20 分。
算法4
因为一个点的点权 $a$ 可以是 $\geq 0$ 的任意数，所以 $i$ 的子树里 (不包括 $i$)，和 $i$ 颜色相同的点的权值和要 $\leq v_i$ ，那么显然权值和要越小越好 。 那么可以参考算法 2 ，此时不需要两维 dp 了，只需要用 $f_i$ 表示 $i$ 的子树里和 $i$ 颜色不同的点的权值和的最小值。 因为这部分数据里一个点的儿子最多只有 $16$ 个，可以用 $2^{16}$ 枚举每个儿子 $j$ 和 $i$ 的颜色是否相同，若相同，则它的贡献是 $v_j$，否则贡献是 $f_j$，然后更新一下 $f_i$，从底向上 DP 。 时间复杂度 $O(n \cdot 2^{16})$，期望得分 20 分。
算法5
算法 4 已经很接近标算了。 只需要把算法 4 中 $2^16$ 的 0,1 枚举改成背包即可。 时间复杂度 $O(nv)$，期望得分 100 分。
B
基础知识
https://en.wikipedia.org/wiki/Laplacian_matrix
Laplacian matrix for ''simple graphs''
Given a simple graph $G$ with $n$ vertices, its Laplacian matrix $L_{n \times n}$ is defined as
$$L = D - A$$
where $D$ is the degree matrix and $A$ is the adjacency matrix of the graph. Since $G$ is a simple graph, $A$ only contains 1s or 0s and its diagonal elements are all 0s.
In the case of directed graphs, either the indegree or outdegree might be used, depending on the application.
The elements of $L$ are given by
$$L_{i,j} := \begin{cases} \deg(v_i) & \mbox{if}\ i = j \\ -1 & \mbox{if}\ i \neq j\ \mbox{and}\ v_i \mbox{ is adjacent to } v_j \\ 0 & \mbox{otherwise} \end{cases} $$
where $\operatorname{deg}(v_i)$ is the degree of the vertex $i$.
Symmetric normalized Laplacian
The symmetric normalized Laplacian matrix is defined as:
$$L^\text{sym} := D^{-\frac{1}{2}} L D^{-\frac{1}{2}} = I - D^{-\frac{1}{2}} A D^{-\frac{1}{2}}$$
The elements of $L^\text{sym}$ are given by
$$L^\text{sym}_{i,j} := \begin{cases} 1 & \mbox{if } i = j \mbox{ and } \deg(v_i) \neq 0\\ -\frac{1}{\sqrt{\deg(v_i)\deg(v_j)}} & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j \\ 0 & \mbox{otherwise}. \end{cases}$$
Random walk normalized Laplacian
The random-walk normalized Laplacian matrix is defined as:
$$L^\text{rw} := D^{-1}L = I - D^{-1}A$$
The elements of $L^\text{rw}$ are given by $$L^\text{rw}_{i,j} := \begin{cases} 1 & \mbox{if } i = j \mbox{ and } \deg(v_i) \neq 0\\ -\frac{1}{\deg(v_i)} & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j \\ 0 & \mbox{otherwise}. \end{cases}$$
Generalized Laplacian
The generalized Laplacian $Q$ is defined as:
$$\begin{cases} Q_{i,j} < 0 & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j\\ Q_{i,j} = 0 & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is not adjacent to } v_j \\ \mbox{any number} & \mbox{otherwise}. \end{cases}$$
Notice the ordinary Laplacian is a generalized Laplacian.
Adjugate matrix
The adjugate matrix $\operatorname{adj}(A)$ is the transpose of the matrix of the cofactors, that is, : $(\operatorname{adj}(A))_{ij} = (-1)^{i+j} M_{ji}.$
For every matrix, one has
$$(\det A) I = A\operatorname{adj}A = (\operatorname{adj}A)\,A. $$
Thus the adjugate matrix can be used for expressing the inverse of a [[nonsingular matrix]]:
$$A^{-1} = \frac 1{\det A}\operatorname{adj}A. $$
暴力：
60 分做法：我们只需要枚举每条边，看看这条边出现在多少个树形图中，将这个值乘上边权，累加就是答案了。
如何求这条边在多少个树形图中呢？可以用补集转换，先求出树形图的总数；然后将这条边从图上删去，即在矩阵上加加减减，求出树形图个数，两者相减就是我们所要的值。
每次求一遍行列式，效率为 $O(mn^3)$
标算
容易发现，求解的 $m$ 次行列式，每次只会修改矩阵某一行的两个值。运用简单的线性代数知识，可以求出基尔霍夫矩阵的伴随矩阵，就可以 $O(1)$ 计算行列式了！
至于伴随矩阵，可以求出逆矩阵，乘上行列式即可；至于逆矩阵， 和原矩阵一起消元就可以啦！$O(m+n^3)$
C
The lower bound on the number of groups if $k$ is odd is $\sum_{i=\frac{k+1}{2}}^k \binom ni$: all subsets of size at least $\frac{k+1}{2}$ have to belong to different groups. Similarly, if $k$ is even, the lower bound is $\frac{1}{2} \binom{n}{k/2} + \sum_{i=k/2+1}^k \binom ni$.
Note that $\binom ni \geq \binom {n}{k-i}$ when $i \geq k/2$. Hence, if we can match all subsets of size $i$ with subsets of size $k-i$ into non-intersecting pairs without common elements, we can achieve the lower bound.
Such a matching always exists when $i \ne k-i$, since the graph is bipartite and “regular” (not exactly, but all vertices in each part have equal degrees). When $k$ is even, the graph is not bipartite, but it turns out that forming $\left\lfloor \frac{1}{2}\binom{n}{k/2} \right\rfloor$ pairs of subsets of size $\frac k2$ is always possible for $n \leq 17$. Even though the graphs are huge, we can build them and try to find maximum matchings: using Kuhn’s algorithm for bipartite graphs, and using Edmonds’ blossom algorithm (or maybe Kuhn’s algorithm with hacks...) for non-bipartite graphs. Even though time complexity looks big, a greedy initialization already builds a huge part of the matching, and augmenting chains are very short on average too. You can try all possible test cases to make sure your solution is fast enough.
If you know a constructive way to build the matchings, or if you have a proof that an optimal matching of subsets of size $\frac k2$ for even $k$ always exists, please share!