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$ 最多会有两条支链，那么两条支链排序后对应相加即可。正确性显然。考虑把这个东西扩展到树上。每个节点维护一个堆，然后向上启发式合并即可。时间复杂度为 $O(n\log n)$ 。代码// ================================= // author: M_sea // website: http://...