我们可以发现每个点集要么是一个链，要么是不同子树中的许多点。
那么显然，如果我们想要取一个链作为集合，那么只有把这个链一直取到叶子才是最优的。
那么我们考虑把这棵树做长链剖分，假设我们得到了 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记录。