题意

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

　　$n\leq 500000$

题解

　　直接贪心从下往上取。对于当前节点，如果选择一些子树之后，超出限制了，就断掉最深的子树，直到最深深度不超过限制就好了。

代码

#include 
     
      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 
      
        a[N];void solve(int x,int pre){	vector 
       
         &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

转载于:https://www.cnblogs.com/zhouzhendong/p/51Nod1367.html

你可能感兴趣的文章