LOJ分析如果 $x$ 关注了 $y$，则从 $x$ 向 $y$ 连一条边。这样子会得到若干个强连通分量。考虑某一个强连通分量。假设它的大小为 $s$，且有 $k$ 条入边，则它对答案的贡献为 $s(s-1)+sk$。考虑维护强连通分量。用并查集维护连通关系，用 std::set 维护入边。假设现在要加入一条边 $x\to y$，讨论一下如果 $x,y$ 在一个强连通分量中，什么都不做。如果...
LuoguLOJ分析看题解发现一个神仙做法。发现我们要求的是一个类似于 LIS 的东西，我们随便取个名字叫树上 LIS。对于每个节点维护一个 multiset ，满足它的第 $i$ 个元素表示子树中选 $i$ 个点的所有树上 LIS 中最小的 $w$ 的最大值。可以发现每个节点的答案就是它的 multiset 的大小。考虑怎么更新。首先把所有子节点的 multiset 启发式合并上来，然后再...
LuoguBZOJ分析先考虑一条链的情况：如果 $1$ 是端点，那么显然只能每个程序单独成一段，答案即为 $\sum M_i$；如果 $1$ 不是端点，那么两条子链中的最大值分成一段、次大值分成一段、…… 是最优的，可以用两个堆维护。考虑扩展到树上。对每个节点开一个堆维护其划分成的若干段的最大值，每次与子节点启发式合并即可。代码// =============================...