题解 CF958B2 【Maximum Control (medium)】

Crab_Dave · 2021-01-08 21:38:13 · 题解

CF958B2 题解

• 题意

  给你一颗由 n 个点组成的树（1\leq n\leq 10^5）。对于一个点集 S,它所占领的点为：

  • 点集 S 中的所有点
  • 对于任意 u,v \in S，u 到 v 路径上的点。

  现在问你当点集的大小分别为 1 到 n 时， 占领的点的数量最大是多少？

• 思路

  从最简单的情况入手。

  显然 k=1 时，ans = 1。

  显然 k=2 时，我们选取树的直径作为最优的路径。

  当 k=3 时，我们考虑在直径外另找一个点，显然最优的方案是选择一个叶子节点。

  我们可以一次dfs求出每个点子树中最深的叶子节点，那么贪心在直径上选取即可。

  这个思想和轻重链剖分的思想好像啊。 所以就按照差不多的思路剖分就好了。

• 代码

  dfs1 求出直径的一端，dfs2 和剖分思路相同，求出重儿子，dfs3 处理出轻重儿子的答案，然后贪心选取。

  #include<bits/stdc++.h>
  using namespace std;
  
  #define ll long long
  const int maxn=1e5+5;
  int n,u,v,rt,d[maxn],son[maxn],h[maxn];
  int head[maxn],cnt;
  struct edge{
  int to,next;
  }e[maxn<<1];
  vector<int>val;
  
  void adde(int u,int v){
  e[++cnt].to=v;
  e[cnt].next=head[u];
  head[u]=cnt;
  }
  
  void dfs1(int u,int fa){
  d[u]=d[fa]+1;int num=0;
  for(int i=head[u];i;i=e[i].next){
      int v=e[i].to;if(v==fa)continue;
      dfs1(v,u);num++;
  }if(!num){if(!rt||d[u]>=d[rt])rt=u;}
  }
  
  void dfs2(int u,int fa){d[u]=d[fa]+1;h[u]=d[u];
  for(int i=head[u];i;i=e[i].next){
      int v=e[i].to;if(v==fa)continue;
      dfs2(v,u);h[u]=max(h[u],h[v]);
      if(!son[u])son[u]=v;
      else if(h[son[u]]<h[v])son[u]=v;
  }
  }
  
  void dfs3(int u,int fa,int tp){
  if(!son[u]){val.push_back(d[u]-d[tp]);return;}
  dfs3(son[u],u,tp);
  for(int i=head[u];i;i=e[i].next){
      int v=e[i].to;if(v==fa)continue;
      if(v==son[u])continue;
      dfs3(v,u,u);
  }
  }
  
  int main(){
  scanf("%d",&n);
  for(int i=1;i<n;i++){
      scanf("%d%d",&u,&v);
      adde(u,v);adde(v,u);
  }rt=0;ll ans=0;
  dfs1(1,0);dfs2(rt,0);dfs3(rt,0,0);printf("1 ");
  sort(val.begin(),val.end(),greater<int>());
  for(int i=2;i<=n;i++){
      if(i-2<val.size())ans+=val[i-2];
      printf("%lld ",ans);
  }return 0;
  }