更好的阅读体验：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/19359481

首先，这个题目的建图太抽象了，需要好好理解一下。

然后我们考虑树上背包。

我们定义 $f_{u, j}$ 表示，在 $u$ 这颗子树内选择 $j$ 个叶子节点的最大收益（叶子点权和 $-$ 需要的边权和）。

那么我们显然有转移：

$$

f_{u, j} = \max{f_{u, j}, f_{u, j - k} + f_{v, k} + w(u, v)}

$$

显然如果你选择了 $v$ 这个子树所产生的收益，那么你就必须承担 $u - v$ 这条边的代价。

然后随便作一些上下界优化即可。

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

考虑树上背包。

定义状态 $f_{u, j}$ 表示 $u$ 节点，切掉 $j$ 个所需的最小花费。

那么我们的初始状态就是 $f_{u, 0} = 0$, $f_{u, sz_u} = 1$。

然后我们考虑如何进行转移：

$$

f_{u, j} = \min(f_{u, j}, f_{u, j - k} + f_{v, k})

$$

然后考虑我们的答案如何进行计算，显然是 $f_{u, sz_u - p} + f_{u, sz_u}$，这个地方的 $f_{u, sz_u}$ 的值显然是 $1$，但是只有根节点是 $0$。

这个地方实际上就是为了让你的选出来的这 $p$ 个点与你原来的 $u$ 子树脱离，显然需要你删一条父边。

更好的阅读体验：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$，找交集最大的边，判断是否合法。

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