[POI 20 Stage 2] Triumphal arch

作法：

首先最外層二分答案，那麼這個問題就可以看成一個遊戲：先手是工人們，後手是國王，先手每次可以把樹上的 k 個點塗黑，後手可以移動到一個相鄰的點。如果後手移動到沒有塗黑的點就贏了。一開始國王在 1 號節點，且 1 已經被塗黑了，問先手是否必勝。

而這只要對每個子樹DP出：若國王現在在這個子樹的根，並且根已經塗黑了，那麼這棵子樹裡必須要預先塗好至少幾個黑點才能讓先手獲勝，這樣就不難列出轉移式了，並且最後如果整棵樹還需要預先塗好 > 0 個黑點的話就會是後手贏，否則先手贏。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=300000+10 ;
 
vector<int> v[maxn] ;
 
int dfs(int x,int f,int num)
{
     if(x!=1 && v[x].size()==1) return 0 ;
     int val=0 ;
     for(int i=0;i<v[x].size();i++) if(v[x][i]!=f)
          val+=dfs(v[x][i],x,num)+1 ;
     return max(0,val-num) ;
}
 
main()
{
     int n ; 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 l=-1 , r=n-1 ;
     while(r-l>1)
     {
          int mid=(r+l)/2 ;
          if(dfs(1,1,mid)==0LL) r=mid ;
          else l=mid ;
     }
     printf("%d\n",r) ;
}