对于第一问答案就是 ∑(du[i]−1)/2+1 对于第二问先二分答案，对于一个非根的点，一定有一条从父亲向下的链，设f[i]表示到点i父亲往下的链最短长度。 将当前点的所有儿子的 f[son[i]]+1 放到一起排个序。 二分f[i]的位置，检验时去掉二分位置的值，贪心每次拿一个最小的匹配最大的（组成一条链），如果儿子总数是偶数把剩余的最大的单独形成一条链（对于根不适用）。 如果儿子总数是偶数并且可以直接两两匹配那么f[i]=0（根节点必须这样匹配）。
#include <bits/stdc++.h> using namespace std; #define N 21000 int n,tot,ans; int head[N],nex[N<<1],to[N<<1]; int du[N],f[N]; vector<int>vec[N]; void add(int x,int y) { tot++; nex[tot]=head[x];head[x]=tot; to[tot]=y; } int calc(int x,int pos,int sz,int v) { int pos1=-1; if(~sz&1) { if(pos!=sz-1)pos1=sz-1; else pos1=sz-2; } for(int i=0,j=sz-1;i<j;i++,j--) { while(i==pos||i==pos1)i++; while(j==pos||j==pos1)j--; if(i>=j)break; if(vec[x][i]+vec[x][j]>v)return 0; } return 1; } int dfs(int x,int y,int v) { for(int i=head[x];i;i=nex[i]) if(to[i]!=y) { if(!dfs(to[i],x,v)||f[to[i]]+1>v) return 0; vec[x].push_back(f[to[i]]+1); } sort(vec[x].begin(),vec[x].end()); int sz=vec[x].size(); if(!sz){f[x]=0;return 1;} int l=0,r=sz-1; if(!calc(x,r,sz,v))return 0; while(l<=r) { int mid=(l+r)>>1; if(calc(x,mid,sz,v))r=mid-1; else l=mid+1; } f[x]=vec[x][l]; if(~sz&1) { int flag=0; for(int i=0,j=sz-1;i<j;i++,j--) if(vec[x][i]+vec[x][j]>v) flag=1; if(!flag)f[x]=0; else if(x==1)return 0; } return 1; } int check(int x) { for(int i=1;i<=n;i++) vec[i].clear(); return dfs(1,0,x); } int main() { //freopen("tt.in","r",stdin); scanf("%d",&n); for(int i=1,x,y;i<n;i++) { scanf("%d%d",&x,&y); add(x,y);add(y,x); du[x]++;du[y]++; } ans+=(du[1]+1)/2; for(int i=2;i<=n;i++) ans+=(du[i]-1)/2; int l=0,r=n-1; while(l<=r) { int mid=(l+r)>>1; if(check(mid))r=mid-1; else l=mid+1; } printf("%d %d\n",ans,l); return 0; }