Article From:https://www.cnblogs.com/yanshannan/p/9687099.html

https://www.zybuluo.com/ysner/note/1289972

surface”

Give a tree at least how many disjoint chains it needs to cover the whole tree, and on this basis minimize the length of the longest chain.

  • \(n\leq10^4\)

    \(k\)A son has\(k\)Strip chain. We can take this.\(k\)22 pairs of chains, if there are more chains, extend to that point. Form\(\lfloor\frac{k}{2}\rfloor\)Strip chain (The number of statistics at the highest point of the chain.)。
    Root node\(1\)No father, so formed.\(\lceil\frac{k}{2}\rceil\)Strip chain.

“The minimum value of the maximum value obviously needs two points.
First two points answer.
set up\(f[u]\)To extend from bottom to top.\(u\)The length of the chain.
Then at each point, merge the longest and the shortest chains of the son, and the secondary long and the secondary short chains… Try to make all chain lengths meet the requirements.
On the basis of meeting the requirements, make the length of the extended chain as short as possible.
Here can be two points, two points that upward chain.

But be careful.
There is a situation:It is not necessary to have an even number of sons at a certain point.\(k\)The chain is finished one by one, one chain unmatched and the other chain extending upward.

Complexity\(O(nlogn)\)
There are some small details. (see the marked line)

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#define ll long long
#define re register
#define il inline
#define pb(a) push_back(a)
#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 N=1e5+100;
int n,h[N],cnt,in[N],ans,f[N],tot;
struct Edge{int to,nxt;}e[N<<1];
vector<int>son[N];
il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};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 int calc(re int u,re int p,re int w)
{
  re int l=-1,r=tot;
  while(l<r)
    {
      ++l;--r;
      if(l==p) ++l;if(r==p) --r;
      if(son[u][l]+son[u][r]>w) return 0;
    }
  return 1;
}
il int dfs(re int u,re int fa,re int w)
{
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      if(!dfs(v,u,w)) return 0;//
      son[u].pb(f[v]+1);
    }
  if(!son[u].size()) {f[u]=0;return 1;}//
  if(u!=1&&son[u].size()%2==0) son[u].pb(0);
  sort(son[u].begin(),son[u].end());
  tot=son[u].size();
  if(u==1&&tot%2==0)
    {
      f[u]=0;
      if(!calc(u,-10,w)) return 0;
    }
  else 
    {
      re int l=0,r=tot-1,p=-1;
      while(l<=r)
      {
        re int mid=l+r>>1;
        if(calc(u,mid,w)) p=mid,r=mid-1;
        else l=mid+1;
      }
      if(p==-1) return 0;
      f[u]=son[u][p];
    }
  return f[u]<=w;//
}
il int check(re int x)
{
  fp(i,1,n) son[i].clear(),f[i]=0;
  return dfs(1,0,x);
}
int main()
{
  freopen("2067.in","r",stdin);
  freopen("2067.out","w",stdout);
  memset(h,-1,sizeof(h));
  n=gi();
  fp(i,1,n-1)
    {
      re int u=gi(),v=gi();
      add(u,v);add(v,u);++in[u];++in[v];
    }
  ans+=(in[1]+1)/2;
  fp(i,2,n) ans+=(in[i]-1)/2;
  printf("%d ",ans);
  re int l=1,r=n,ans=1;
  while(l<=r)
    {
      re int mid=l+r>>1;
      if(check(mid)) ans=mid,r=mid-1;
      else l=mid+1;
    }
  printf("%d\n",ans);
  return 0;
}
Link of this Article: [Poi2004]SZN

Leave a Reply

Your email address will not be published. Required fields are marked *