原文链接https://www.cnblogs.com/zhouzhendong/p/51Nod1367.html
题目传送门 - 51Nod1367
题意
有一棵N个点的树，树中节点标号依次为0,1,2,...N-1，其中N<=500000。树中有N-1条边，这些边长度不一定相同。现在要把树中一些边删除，设删除了K条边（K>=0，即可以不删除任何边），由树的性质可知，该树将被分割为一个含有K+1棵树的森林。称一个森林是"完美森林"，要求这个森林中的每一棵树满足：该树的直径长度不超过MAXDIST这么长。其中树的直径指树中任意两点的最大距离。那么，对于给出的N个点的树，能划分出的完美森林最少包含多少棵树？
$n\leq 500000$
题解
直接贪心从下往上取。对于当前节点，如果选择一些子树之后，超出限制了，就断掉最深的子树，直到最深深度不超过限制就好了。
代码
#include <bits/stdc++.h>
using namespace std;
int read(){
int x=0;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
const int N=500005;
struct Graph{
static const int M=N*2;
int cnt,y[M],z[M],nxt[M],fst[N];
void clear(){
cnt=1;
memset(fst,0,sizeof fst);
}
void add(int a,int b,int c){
y[++cnt]=b,nxt[cnt]=fst[a],fst[a]=cnt,z[cnt]=c;
}
}g;
int n,m,ans=1;
int dis[N];
vector <int> a[N];
void solve(int x,int pre){
vector <int> &v=a[x];
v.clear();
v.push_back(0);
for (int i=g.fst[x];i;i=g.nxt[i])
if (g.y[i]!=pre){
solve(g.y[i],x);
v.push_back(dis[g.y[i]]+g.z[i]);
}
if (!v.empty())
sort(v.begin(),v.end());
while (!v.empty()&&v.back()>m)
v.pop_back(),ans++;
while (((int)v.size())>=2&&v.back()+v[(int)v.size()-2]>m)
v.pop_back(),ans++;
dis[x]=v.back();
v.clear();
}
int main(){
n=read(),m=read();
for (int i=1;i<n;i++){
int a=read()+1,b=read()+1,c=read();
g.add(a,b,c);
g.add(b,a,c);
}
solve(1,0);
printf("%d",ans);
return 0;
}