Description：

给你棵树，要求把叶子节点分成尽量少的集合使得每个集合内叶子节点两两间距离不超过给定的 $k$ 。

$1\leqslant n\leqslant 10^6$

Solution：

每个点维护一个当前还没断的最长链，每到一个点处理完他的所有子树后把他所有子树的最长链拿出来排序，找到最后一个 $s[i]+s[i-1]\leqslant k$ 的位置，把前面的都合到 $i$ 这条链上传递给他的父亲，，后面的只能每个都分一个集合，把答案累加这么多即可，注意最后加一因为有一个集合的最长链被留到了根节点。

想不到。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,l;

#define MAXN 1000010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

int deg[MAXN];

void add(int a,int b)

{

	++deg[a];++deg[b];

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

bool v[MAXN];

int ans = 0;

int dfs(int k)

{

	v[k] = true;

	vector<int> s;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		s.push_back(dfs(e[i].to) + 1);

	}

	if(s.size() == 0)return 0;

	sort(s.begin(),s.end());

	for(int i = 0;i < s.size() - 1;++i)

	{

		if(s[i] + s[i + 1] <= l)continue;

		else

		{

			ans += s.size() - i - 1;

			return s[i];

		}

	}

	return s[s.size() - 1];

}

int main()

{

	scanf("%d%d",&n,&l);

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	int rt = 0;

	for(int i = 1;i <= n;++i)

	{

		if(deg[i] != 1)rt = i;

	}

	dfs(rt);

	cout << ans + 1 << endl;

	return 0;

}