Comet OJ Contest #2 D 错综的光影所迷惑的思念是
Comet OJ 分析 可以发现一个点集的所有直径的中点都相同。为了方便我们把边也拆成点，这样子中点一定是一个点。 枚举中点和半径，那么深度小于半径的点任意选，深度等于半径的必须有至少两棵子树中选了，容斥一下即可。 代码 // ==================================== // author: M_sea // website: https://m-sea...
Comet OJ 分析 可以发现一个点集的所有直径的中点都相同。为了方便我们把边也拆成点，这样子中点一定是一个点。 枚举中点和半径，那么深度小于半径的点任意选，深度等于半径的必须有至少两棵子树中选了，容斥一下即可。 代码 // ==================================== // author: M_sea // website: https://m-sea...
Conspiracy 考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。 于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。 可能会有些卡空间。 代码 Lollipop 可以发现如果存在一段和为 $w$，则一定存在一段和为 ...
传送门 勇者比太郎 看懂题后可以发现，我们要求每个 J 右边的 O 的数量乘下面的 I 的数量之和。 预处理前缀和后枚举每个 J 计算即可。 代码 画展 先以 $V_i$ 为第一关键字、$S_i$ 为第二关键字对所有画排个序，以 $C_i$ 为关键字对所有画框排序。 然后从后往前扫，如果当前的画能装进没有装画的 $C$ 最大的画框里，就把它装进去。 正确性比较显然？反正我不会证 代码 有趣的...
Codeforces Luogu 分析 显然选的路径是直径的一部分。为了方便，把直径上的点重编号为 $1\sim cnt$。 我们把这棵树想象成一条链上挂了一些子树。那么设一个 $maxdis_i$ 表示 $i$ 子树中到 $i$ 最远的点的距离。 一个暴力做法是枚举选的路径 $[l,r]$，此时最大距离就是 $1\sim l$ 的距离、$r\sim cnt$ 的距离、$\max_{i=l}...
CodeForces 分析 直接考虑删哪条似乎很不可做的样子，我们考虑枚举删掉哪条然后快速算直径。 把环拉出来，这样子每个环上的点就对应了一颗子树。 显然我们只能删掉环上的边。这里为了表述方便，把环上的点顺时针重编号为 $1\sim sz$ 。 假设当前删掉了 $(x-1,x)$ 。设 $f[i]$ 表示 $i$ 的子树中的节点到 $i$ 的最长路径长度， $sum[i]$ 表示 $i$ 逆...