考完联赛后重写了一下题库，把一些旧的模块废除了。

以后题目的官方题解、std及相关资料我会直接挂在题库里，拥有该题目权限的用户可直接查看。

大家自己的模拟赛题的题解可以直接在博客中写，写完以后可以选择上传至题目的题解区。当然你也可以将你的题解文件上传至题解内。（拥有 upload-editorial 权限的用户可以直接上传，否则将会提交管理员审核）

其他题目的题解仍然在博客中编写，写完后可以设置可见权限。

感谢无敌的 zlt、cgl 提供的建议

orz ysx

Read more...

A

先求一个最短路图 然后再这个图上dfs 对于一个点的所有出点 按编号从小到大dfs。这样可以保证dfs树就是题目要求的树。

然后在这棵树上跑树分治 $f{i,j,0/1/2}$ 表示前i棵子树 从根出发链长为j [0：最长长度][1:这个长度条件下的方案数]

对于第 $i+1$ 棵子树 单独跑一个 $f'_{i,j,0/1/2}$ 意义一样 枚举这颗子树上链长 和f一起更新答案 然后用 $f'$ 更新 $f$

B

首先对于两个重心的情况，可以在中间加一个点，变为一个重心的情况。 树形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$，则这个根为唯一重心。

剩余的部分就很显然了。

C

显然答案为 $\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)$ 计算答案