视察

贪心

题面

给一棵树，要求在选取的点与点之间，距离不小于$l$的前提下，最大化点的数量。

• $n\leq5*10^5$

解析

贪心原则是：随便找个点为根，用堆维护当前深度最大的点，选取它作为答案之一，然后把离他距离小于$l$的点删掉，依此类推。
证明？？？
我只能猜这是因为深度越大，选取该点对选取其它点影响越小。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=1e9+7,N=1e6+100;
struct Edge{int to,nxt,w;}e[N<<1];
int in[N],h[N],cnt,n,t,ans,tot,d[N],pos,mx;
bool vis[N];
struct node{int dis,u;bool operator < (const node &o) const {return dis<o.dis;}};
priority_queue<node>Q;
il void add(re int u,re int v,re int w)
{
  e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;
}
il ll gi()
{
   re ll x=0,t=1;
   re char ch=getchar();
   while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
   if(ch=='-') t=-1,ch=getchar();
   while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
   return x*t;
}
il void pre(re int u,re int fa)
{
  d[u]=d[fa]+1;if(d[u]>mx) mx=d[u],pos=u;
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      pre(v,u);
    }
}
il void dfs(re int u,re int fa,re int dd)
{
  Q.push((node){dd,u});
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      dfs(v,u,dd+e[i].w);
    }
}
il void find(re int u,re int fa,re int dis)
{
  //printf("%d %d %d\n",u,fa,dis);
  if(dis<t) vis[u]=1;else return;
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      find(v,u,dis+e[i].w);
    }
}
il void solve()
{
  while(!Q.empty())
    {
      while(!Q.empty()&&vis[Q.top().u]) Q.pop();
      if(!Q.empty())
    {
      re int u=Q.top().u;Q.pop();++ans;//printf("%d\n",u);
          find(u,u,0);
    }
    }
}
int main()
{
  freopen("inspect.in","r",stdin);
  freopen("inspect.out","w",stdout);
  memset(h,-1,sizeof(h));
  n=gi();t=gi();
  fp(i,1,n-1)
    {
      re int u=gi(),v=gi(),w=gi();
      add(u,v,w);add(v,u,w);in[u]++;in[v]++;
    }
  pre(1,0);
  dfs(pos,pos,0);
  solve();
  printf("%d\n",ans);
  fclose(stdin);
  fclose(stdout);
  return 0;
}