似乎 BZOJ 挂了以后就没有地方有 JSOI 2017 的题目了，于是上传了一下。
Enjoy!
这篇博客可以公开，就公开了。
$O(2^n)$ 枚举一下每个点染成什么颜色，然后从底向上 确定每一个点的权值， 如果所有点的权值都 $\geq 0$，则这是一组合法解，输出 POSSIBLE 否则继续做。
若没有合法解，则输出 IMPOSSIBLE。
时间复杂度 $O(n \cdot 2^n)$，期望得分 20 分。
可以考虑用树形 DP 来做。用 $f_{i,j}$ 表示 $i$ 的子树里和 $i$ 颜色不同的点的权值和为 $j$ 可不可行。 从底向上树形 DP 即可。
时间复杂度 $O(nv^3)$，期望得分 40 分。
因为这部分数据是一条链， 从底向上 dp 用 $f_{i,j}$ 表示是否存在一个合法方案满足上一个与 $i$ 颜色不同的节点是 $j$ 转移的时候， 对于 $i$ 号点 ，枚举上一个和它颜色相同的点 $k$ ，如果 $f_{i+1,k}=\mathsf{true}$ 且 $v_i\geq v_k$，那么这就是一种合法方案。
时间复杂度 $O(n^2)$，期望得分 20 分。
因为一个点的点权 $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 分。
算法 4 已经很接近标算了。 只需要把算法 4 中 $2^16$ 的 0,1 枚举改成背包即可。 时间复杂度 $O(nv)$，期望得分 100 分。
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)$
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!
简单题。
为了全真模拟, 接下来训练中下发文件将设置密码.
由于太懒导致 FTP 上下发文件没备注密码, 因此相关密码会备注在这个帖子里.
LetsORZTeacherChenThisContestWillBeRatedOnQ0j1AkN0ipno1WCaPiohioadiogfhdhasdhifhaozaiqiangmeiyou____pleaseContactLYDSY20121PswordIsStrong!Psw0rdIsNotWeak?wjsswsjbxlZYCWZYKLittleQAndHerKeyTitleEyeReallyWaterIAKWalkPeoplej01wh9df$YdoUalwaysAKop3nTrain5.$narknews.1nf0qwertyuioplkjhgfdsazxcvbnm考完联赛后重写了一下题库，把一些旧的模块废除了。
以后题目的官方题解、std及相关资料我会直接挂在题库里，拥有该题目权限的用户可直接查看。
大家自己的模拟赛题的题解可以直接在博客中写，写完以后可以选择上传至题目的题解区。当然你也可以将你的题解文件上传至题解内。（拥有 upload-editorial 权限的用户可以直接上传，否则将会提交管理员审核）
其他题目的题解仍然在博客中编写，写完后可以设置可见权限。
感谢无敌的 zlt、cgl 提供的建议
orz ysx
先求一个最短路图 然后再这个图上dfs 对于一个点的所有出点 按编号从小到大dfs。这样可以保证dfs树就是题目要求的树。
然后在这棵树上跑树分治 $f{i,j,0/1/2}$ 表示前i棵子树 从根出发链长为j [0：最长长度][1:这个长度条件下的方案数]
对于第 $i+1$ 棵子树 单独跑一个 $f'_{i,j,0/1/2}$ 意义一样 枚举这颗子树上链长 和f一起更新答案 然后用 $f'$ 更新 $f$
首先对于两个重心的情况，可以在中间加一个点，变为一个重心的情况。 树形dp，$f_{i,j}$ 表示以 $i$ 为根的子树 大小为 $j$ 的方案数，转移可以用背包把一个根的所有子树合并
计算 $f$ 数组复杂度 $O(n^3)$
然后对于根求 $g_{i,j,k}$ 表示前 $i$ 棵子树 最大节点数 $\leq j$ 节点数和为 $k$ 的方案数，更新用背包更新，直接枚举当前子树取多少，前面的一共取多少什么，如果直接这样做，复杂度 $O(n^4)$，可以把根的所有子树按size从小到大排序 这样就可以保证对于 $i,j$ 只要枚举 $O(\mathrm{siz}_i)$ 即共为 $\sum \mathrm{siz}_i = n$ 降了一维。
然后枚举最大的子树的大小，设为 $k$，只要满足总节点数 $v > 2k$，则这个根为唯一重心。
剩余的部分就很显然了。
显然答案为 $\min\left(\sum \frac{(kx_i-y_i+b)^2}{k^2 + 1}\right)$
可以三分套三分算出最优解
展开可以发现只要预处理出 $\sum x_i、\sum y_i、\sum x_i^2、\sum y_i^2、\sum x_iy_i$
就可以 $O(1)$ 计算答案