题意

有一棵N个点的树，树中节点标号依次为0,1,2,…N-1，其中N<=500000。树中有N-1条边，这些边长度不一定相同。现在要把树中一些边删除，设删除了K条边（K>=0，即可以不删除任何边），由树的性质可知，该树将被分割为一个含有K+1棵树的森林。称一个森林是”完美森林”，要求这个森林中的每一棵树满足：该树的直径长度不超过MAXDIST这么长。其中树的直径指树中任意两点的最大距离。那么，对于给出的N个点的树，能划分出的完美森林最少包含多少棵树？

题解

很简单的一个题啊。。
dfs一下
每一个节点维护包含他的子树，最长的链是什么
然后如果一起合并到父亲，发现直径不符合要求了
就从大往小删
就可以了
时间复杂度O(nlogn)
不懂就看代码吧。。代码也很短

废话

想了一个下午，想两题
还有一个是1411 矩阵取数问题 V3
这题几分钟想完了。。
然后另外一题想了一个下午。。最后发现是插头DP。。以后搞插头DP的时候再做了QAQ
感觉又点浪费时间

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
const int N=500005;
int n,size;
struct qq
{int x,y,z,last;
}e[N*2];int num,last[N];
void init (int x,int y,int z)
{num++;e[num].x=x;e[num].y=y;e[num].z=z;e[num].last=last[x];last[x]=num;
}
int o[N];//这个子树的最深深度是什么 
int ans=1;
void dfs (int x,int fa)
{//printf("%d\n",x);vector<int> s;for (int u=last[x];u!=-1;u=e[u].last){int y=e[u].y;if (y==fa) continue;dfs(y,x);s.push_back(o[y]+e[u].z);}int t=s.size();if (t==0) return ;sort(s.begin(),s.end());while (t>1){if (s[t-1]+s[t-2]>size) {t--;ans++;}else break;}if (t==1&&s[0]>size)    {ans++;o[x]=0;}else o[x]=s[t-1];
}
int main()
{num=0;memset(last,-1,sizeof(last));scanf("%d%d",&n,&size);for (int u=1;u<n;u++){int x,y,z;scanf("%d%d%d",&x,&y,&z);x++;y++;init(x,y,z);init(y,x,z);}dfs(1,0);printf("%d\n",ans);return 0;
}