P9369 [ICPC2022 Xi'an R] Tree

我们可以发现每个点集要么是一个链，要么是不同子树中的许多点。

那么显然，如果我们想要取一个链作为集合，那么只有把这个链一直取到叶子才是最优的。

那么我们考虑把这棵树做长链剖分，假设我们得到了 p 条长链，每条长链的长度为 lp_i。

假设我们一开始全都用第二类集合来划分，那么答案显然是整棵树最大的深度。这个答案也可以看做是将所有长链的底端对其以后水平放置，同一行的点划分进一个点集的结果，也就是这些长链的最大长度。显然同一行中的点不存在祖先关系。

考虑贪心选择一些长链作为第一个集合，显然因为第二类集合的数量应该是“剩余长链的最大长度”，所以选择最长的长链必然最优。

将 lp_i 从大到小排序，枚举我们选择了前 i 条长链作为第一类集合，那么剩余的长链作为第二类集合的集合数量是 lp_{i+1}，因此答案就是 i+lp_{i+1}。

时间复杂度 O(n)。

部分代码：

void dfs1(int x) {
    for (int y : g[x]) {
        dfs1(y);
        if (len[y] > len[son[x]]) son[x] = y;
    }
    len[x] = len[son[x]] + 1;
}
void dfs2(int x, int l = 0) {
    if (!son[x]) lp.push_back(l);
    else {
        dfs2(son[x], l + 1);
        for (int y : g[x]) if (y != son[x]) dfs2(y, 1);
    }
}

AC记录。