首先最外層二分答案,那麼這個問題就可以看成一個遊戲:先手是工人們,後手是國王,先手每次可以把樹上的 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) ; }
沒有留言:
張貼留言