[CF1042F]Leaf Sets

题目大意：给定一棵$n$个点的树，将叶子节点分为数个集合，使集合里点对最长距离不超过$k$，求最少集合数。

题解：贪心，发现将叶子节点分成集合等于把节点划分集合，答案是一样的。因为一定有一个点，到非叶子节点$p$的儿子的距离比到$p$远。然后发现一个集合一定是连续的（或者连续的一定最优），不然不完全可以把中间连起来，且合法。

$dfs$，如果一个点的最长两个点长度和大于$k$就加一个集合

注意要用非叶子节点当根，最后答案要加一

卡点：没用非叶子节点当根

C++ Code：

#include <cstdio>
#include <vector>
#include <algorithm>
#define maxn 1000010
int head[maxn], cnt;
struct Edge {int to, nxt;
} e[maxn << 1];
inline void add(int a, int b) {e[++cnt] = (Edge) {b, head[a]}; head[a] = cnt;
}
int n, k, ans;
int ind[maxn], fa[maxn], M[maxn];
void dfs(int u) {if (ind[u] < 2) return ;std::vector<int> E;for (int i = head[u]; i; i = e[i].nxt) {int v = e[i].to;if (v != fa[u]) {fa[v] = u;dfs(v);E.push_back(M[v] + 1);}}std::sort(E.begin(), E.end());int now = E.size() - 1;for (; now; now--) if (E[now] + E[now - 1] > k) ans++;else break;M[u] = E[now];
}
int main() {scanf("%d%d", &n, &k);int rt = 1;for (int i = 1, a, b; i < n; i++) {scanf("%d%d", &a, &b);add(a, b), add(b, a);ind[a]++, ind[b]++;if (ind[a] != 1) rt = a;if (ind[b] != 1) rt = b;}dfs(rt);printf("%d
", ans + 1);return 0;
}