題目大意：

給一顆樹，1號節點已經被染黑，其余是白的，兩個人輪流操作，一開始B在1號節點，A選擇k個點染黑，然后B走一步，如果B能走到A沒染的節點則B勝，否則當A染完全部的點時，A勝。求能讓A獲勝的最小的k

?

小的k能獲勝大的k就一定能獲勝，因此答案具有單調性，可以二分答案。

那么每次二分的答案怎么驗證？

樹形DP，設f[i]表示在B沒走到以i為根的子樹中時，需要預先在這棵子樹中染色的節點數。

f[x]=max(0,∑f[to[i]]+son[x]-k)，其中to[i]代表x的子節點，son[x]代表x的子節點數。

每次DP后只要判斷f[1]==0就行了。

#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; int head[300010]; int to[600010]; int next[600010]; int ans; int tot; int f[300010]; int n; int x,y; int mid; void add(int x,int y) {tot++;next[tot]=head[x];head[x]=tot;to[tot]=y; } void dfs(int x,int fa) {int sum=0;for(int i=head[x];i;i=next[i]){if(to[i]!=fa){dfs(to[i],x);sum+=f[to[i]]+1;}}f[x]=max(0,sum-mid); } bool check() {memset(f,0,sizeof(f));dfs(1,0);if(f[1]==0){return true;}return false; } int main() {scanf("%d",&n);for(int i=1;i<n;i++){scanf("%d%d",&x,&y);add(x,y);add(y,x);}int l=0;int r=n+1;while(l<=r){mid=(l+r)>>1;if(check()==true){ans=mid;r=mid-1;}else{l=mid+1;}}printf("%d",ans); }

轉載于:https://www.cnblogs.com/Khada-Jhin/p/9680547.html

總結

以上是生活随笔為你收集整理的BZOJ3420[POI2013]Triumphal archBZOJ5174[Jsoi2013]哈利波特与死亡圣器——树形DP+二分答案...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。