首先考虑判定什么样的选取是合法的。
考虑到令任意一个点 \(u\) 为根。
若 \(u\) 有至少两个子树没有点选中，那么这两个子树是无法区分的。
所以可以知道需要满足任意一个点为根，都至多存在一个子树内部没有选中的点。
接下来就要贪心的选出最少的点了。
考虑对于每个点的限制都是子树。
不难想到把关键点都移到叶子节点肯定最优。
不妨假设所有的叶子节点都要被选中，这样首先肯定是满足条件的。
考虑一个 \(\operatorname{deg} > 2\) 的点 \(u\)，这里必然有几个子树在此合并。
若一个子树其实是一条链，那么能够知道这条链就肯定是不用选的了。
这是因为链内部其实不需要一个关键点，因为如果链上的点为根，那么 \(u\) 这边一定有关键点；如果是链外的非 \(u\) 点为根，链所在的子树肯定存在关键点；如果是 \(u\) 点为根，那么非链的子树有关键点。
不能是非链的子树的原因就是因为此时这个子树中肯定也存在 \(\operatorname{deg} > 2\) 的点，实际上应该交给这个点来决定。
实现时可以考虑直接从叶子节点开始往上跳链。
注意特判下链的情况，这个时候选中一个叶子节点即可，答案为 \(1\)。
时间复杂度 \(\mathcal{O}(n)\)。
#include<bits/stdc++.h>
const int maxn = 1e5 + 10;
std::vector<int> to[maxn];
int vis[maxn];
int main() {
int n; scanf("%d", &n);
for (int i = 1, x, y; i < n; i++)
scanf("%d%d", &x, &y), to[x].push_back(y), to[y].push_back(x);
int mx = 0;
for (int i = 0; i < n; i++)
mx = std::max(mx, (int)to[i].size());
if (mx <= 2)
return puts("1"), 0;
int ans = 0;
for (int i = 0; i < n; i++)
if (to[i].size() == 1) {
int u = i, v = to[i][0];
for (int p; to[v].size() == 2; p = to[v][0] ^ to[v][1] ^ u, u = v, v = p);
ans += (vis[v]++) > 0;
}
printf("%d\n", ans);
return 0;
}