更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19346416

首先考虑 $\mathcal{O}(n ^ 2)$ 的解法。

枚举每条边，然后分别统计左右子树的重心，然后想加即可。

然后考虑优化，显然我们的复杂度浪费在了找重心的地方。

“一棵有根树的重心一定在根结点所在的重链上。一棵树的重心一定是该树根结点重子结点对应子树的重心的祖先。”——OIwiki

有关树的重心的内容见OI-wiki/树的重心

重心必在节点的「重儿子链」上（重儿子指子树大小最大的子节点），因此可通过倍增沿重儿子链快速定位重心候选。

删除边 $(u, v)$ 后，$u$ 所在的大子树（大小 $n - sz_v$）需要「换根」更新重儿子（原重儿子可能是 $v$，需替换为次重儿子或父方向），而 $v$ 所在的小子树（大小 $sz_v$)）是原树的子树，无需换根。

节点最大子树（含父方向）≤ 总大小 / $2$ 则为重心。

递归算每个节点的子树大小，记录重 / 次重儿子（子树最大 / 次大的子节点），构建倍增数组（沿重儿子链跳，$\mathcal{O}(\log n)$ 找重心）。

然后累加答案即可。

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19343265

首先考虑用线段树做。

发现数据范围很大，但是实则不需要考虑啊，因为我们的海报的数量一定，可以考虑离散化去重，然后用线段树做。

每次更改一段区间的话，采用标记延迟下传的方式，如果在目标区间就先打上懒标记，如果以后访问到了再下传，这样就不必要每次放到叶子上了。

最终查询就直接访问所有叶子就好，用个 set 去重海报。

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19369112

要求满足不回家的人和外校的人都有床睡，一个人只会睡自己认识的人的床。

考虑二分图最大匹配。

然后，这个点 $u \to v$ 连边的前置条件是 $v$ 是在校学生，且 $v$ 回家睡觉。

需要注意的是，自己显然是可以睡自己的床的（并非废话），只要这个学生在校且不回家，就可以 $u \to u$。

将图建出来之后，直接跑二分图最大匹配即可。

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19368752

首先就是最大值最小，我们可以考虑进行二分，二分答案 $k$，也就是说当前的所有航线的路程需要小于等于 $k$，我们知道，每次改完，最多能让一个航线的值减去 $1$，我们只需要判断这些大于等于 $k$ 的航线交集最多的那条边即可。

于是我们的思路就出来了，二分 $k$，找交集最大的边，判断是否合法。

然后找交集的过程我们可以采用树上差分。

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19361885

这个题目要求我们把给出的状态通过类似华容道的方式，去移动 $0$ 的位置，然后就可以调整其他数的位置。

然后我们考虑把这个棋盘的状态存下来，这样的话我们就可以直接转移，然后我们显然可以把这玩意直接弄成字符串，为了保证答案的最小，直接字符串 $hash$ 存每个字符串的最小值，然后我们每次关注 $0$ 的位置，进行 bfs 即可，新的状态取最小即可。这种已经可以 AC了。

我们继续考虑优化，这里给出 A* 的写法，我们是否有很多没必要的状态呢？A* 的剪枝就很类似于贪心的思路，我们可以维护一个东西，每次在 bfs 的时候取你觉得比较优的答案。这时候我们需要维护一个估价函数，对于这个题的话，我们可以认为，位置正确的越多，那么这个东西显然很优，先对这些正确位置比较多的进行拓展，那么我们有 $F(S)$ 就是表示当前的状态下正确的位置的个数，然后我们去维护一个小根堆，里面的值是 $S_{now} + F(S)$，这个东西越小显然越优，我们优先去拓展，如果已经到了目标状态，那么就没必要继续搜索了，这个答案一定最优。这个东西就很类似最短路的 dijkstra，每次都取最小的。然后显然我们的 $F(S)$ 是要小于等于实际的可能花费的，因此这样的拓展一定最优。

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19369035

那么，相当于每个党派的两个代表就是两种情况，然后直接按其说的厌恶的关系建边跑 $\text{2 - SAT}$ 即可。

每个党派 $i$ 对应2-SAT的一个布尔变量，其两个代表 $2i$、$2i+1$ 分别对应「变量为真」「变量为假」，题目中“代表a和b互相厌恶” $\to$ 约束：**不能同时选 a 和 b**，即选 a 则必须选 b 的对立代表，选 b 则必须选 a 的对立代表。

先将代表编号转为 $0$ 起始（$a \rightarrow a - 1$），记a对应节点 $u$，b 对应节点 $v$；

互斥约束转化为两条有向边：

 1. $u \rightarrow v \oplus 1$（选 a → 必须选 b 的对立代表）

 2. $v \rightarrow u \oplus 1$（选 b → 必须选 a 的对立代表）

 （$\oplus 1$ 是异或操作，可快速找到每个代表的“对立代表”：偶数变奇数，奇数变偶数）。