[Poi2004]SZN

贪心 二分

题面

给一棵树，问最少要用多少条不相交的链，才能覆盖整棵树；并在此基础上，最小化其中最长链的长度。

• $n\leq10^4$

解析

第一问直接贪心即可。
若该点有$k$个儿子，则有$k$条链。我们可以把这$k$条链两两配对，若有多出的链，就延伸到该点父亲去。则形成$\lfloor\frac{k}{2}\rfloor$条链（在链的最高点统计个数）。
而根节点$1$号没有父亲，所以形成$\lceil\frac{k}{2}\rceil$条链。

“最大值的最小值”问题显然需要二分。
先二分答案。
设$f[u]$为从下往上延伸到点$u$的链的长度。
然后在每个点中，把儿子中最长链与最短链合并，次长链和次短链合并。。。尽量使所有链长符合要求。
在符合要求的基础上，使向上延伸的链的长度尽量短。
这里又可以二分，二分那条向上延伸的链。

但是要注意一点，
存在一种情况：某点有偶数个儿子时，不一定要把$k$条链一一配对完毕；一条链不配对，另一条链向上延伸也是可以的。

复杂度$O(nlogn)$。
有些小细节。（看打了标记的行）

#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;
}