[HOJ 135][POI 11 Stage 1] 縫紉課

作法：

首先可以知道第一個答案就是奇點個數/2。

要求最長的鍊最短，所以當然最外層二分答案。
隨便選一個點當根對樹DFS，每個點 x 回傳「能夠把 x 這個子樹拆成一些長度不超過當前最大長度限制的鍊，和一條終點在 x 的長度為 t 的鍊」的 t 的最小值。

這樣在作完後，分成三種情形：

1. 兒子數目為偶數：
先試著把兩兩兒子配對，如果可以配完並滿足長度限制那就回傳0，而配法可以知道用最長配最短、第二長配第二短、......是最好的。
如果沒辦法配對成功，那麼就選一條留下(等於是這條鍊就到 x 結尾)，轉成兒子數目為奇數的情形。

2. 兒子數目為奇數：
一定會選其中一條傳上去，然後剩下的兩兩配對，而我們希望傳上去的長度越短越好，所以從最小長度的開始試，如果能把他留住並讓剩下的兩兩配對成功就傳他上去，如果一直到最大長度都沒辦法那就代表無解。

這樣的時間複雜度會到 sigma (d_i)^2  (其中 d_i 是點的度)，也就是最壞O(n^2)，不過感覺蠻難構出會讓他跑很慢的測資......@@

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+10 ;
int n ;
vector<int> v[maxn] ;
 
int dfs(int x,int fa,int num)
{
    if(x!=1 && v[x].size()==1) return 0 ;
    vector<int> tmp ;
    for(auto i : v[x]) if(i!=fa)
    {
        int val=dfs(i,x,num) ;
        if(val==-1) return -1 ;
        tmp.push_back(val+1) ;
    }
    sort(tmp.begin(),tmp.end()) ;
    int sz=tmp.size() ;
 
    if(tmp[sz-1]>num) return -1 ;
    if((sz%2)==0)
    {
        bool ok=1 ;
        for(int i=0;sz-1-i>i;i++) if(tmp[i]+tmp[sz-1-i]>num)
            {ok=0 ; break ;}
        if(ok) return 0 ;
        if(x==1) return -1 ;
        tmp.resize(sz-1) ; sz-- ;
    }
 
    for(int i=0;i<sz;i++)
    {
        int l=0 , r=sz-1 , ok=1 ;
        while(r>l)
        {
            if(l==i) l++ ;
            if(r==i) r-- ;
            if(r<=l) break ;
            if(tmp[l]+tmp[r]>num) { ok=0 ; break ; }
            l++ ; r-- ;
        }
        if(ok) return tmp[i] ;
    }
    return -1 ;
}
 
bool check(int num)
{
    return (dfs(1,1,num)!=-1) ;
}
 
main()
{
    scanf("%d",&n) ;
    for(int i=1;i<n;i++)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
    }
 
    int num=0 ;
    for(int i=1;i<=n;i++) if(v[i].size()%2) num++ ;
    printf("%d ",num/2) ;
 
    int l=0 , r=n-1 ;
    while(r-l>1)
    {
        int mid=(r+l)/2 ;
        if(check(mid)) r=mid ;
        else l=mid ;
    }
    printf("%d\n",r) ;
}