ICPC XiAn 2022 L

题目描述

给定一棵树，求最小的链与反链和个数。链必须是从父亲节点到子节点。

反链：任意两个点不处于同一子树的点集。

解题思路

首先我们知道Dilworth定理：最长反链等于最小链覆盖数。

我们在树的情况下猜测最小反链数等于最长链长。

给出如下证明：

如果只有一棵树，那么长链上的点都不能位于同一集合中，因此最小反链数至少是长链长度。对于剩余的点，只需要把它们安排在同一高度的点中即可。因此对于一棵树的情况成立。

对于一个森林，最小反链数至少是长链长度，由以上结论可以证得。对于其它的树，我们也完全可以将同一层的节点提交到相同深度的集合中。因此，证毕。

那么我们看本题，本质上只分为链和反链两种情况。反链的答案对应反链集合中最长的长链长。而对于链的答案，我们可以发现，一条链到达叶子节点覆盖的点数最多。假设有一条不到叶子的链，考虑到叶子节点的剩余节点，如果这些节点属于某一条链，那么拼接两条链，使得数目减少；如果属于一条反链，那么反链森林中的最长链长度减小。因此，证毕。

所以，我们首先做长链剖分，求出所有长链的长度，对这些长链从大到小排序，答案为.