題目鏈接

---

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

? 好像洛谷給的N數據范圍是1e5級別的。

? 于是，如果直接查的話，好想不大好查，但是如果我們現在假設一個答案k，然后呢，我們判斷這個k是否可以滿足這個條件，這樣的做法會更好一些。

? 當我們假設一個k的時候，就可以判斷它的可行性了，如果現在B要往樹的某個方向走，那么它肯定選擇的是最優的策略，因為再返回回來，走回頭路一定不是最優的，現在用dp來輔助這個問題，表示走u的子樹的某條鏈的最多需要被染色的節點的個數（用的是除了這K次以外的次數）。

? 于是，可以確定dp方程：假設u是v的父親節點，是不包含父親節點的度數；

? 其中表示的意思就是，由于我們需要先染色，所以為了避免下一步就直接存在B可以走到未染色的點，所以需要至少個點染色；然后，由于不確定B走的方向，所以還需要知道所有的需要被染色的點的個數，由于有K個可以染色的次數，所以就可以減去K次。

#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <limits> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #include <bitset> #include <unordered_map> #include <unordered_set> #define lowbit(x) ( x&(-x) ) #define pi 3.141592653589793 #define e 2.718281828459045 #define INF 0x3f3f3f3f #define HalF (l + r)>>1 #define lsn rt<<1 #define rsn rt<<1|1 #define Lson lsn, l, mid #define Rson rsn, mid+1, r #define QL Lson, ql, qr #define QR Rson, ql, qr #define myself rt, l, r #define pii pair<int, int> #define MP(a, b) make_pair(a, b) using namespace std; typedef unsigned long long ull; typedef unsigned int uit; typedef long long ll; const int maxN = 1e5 + 7; int N, du[maxN] = {0}; namespace Graph {int head[maxN], cnt;struct Eddge{int nex, to;Eddge(int a=-1, int b=0):nex(a), to(b) {}} edge[maxN << 1];inline void addEddge(int u, int v){edge[cnt] = Eddge(head[u], v);head[u] = cnt++;}inline void _add(int u, int v) { addEddge(u, v); addEddge(v, u); du[u]++; du[v]++; }inline void init(){cnt = 0;for(int i=1; i<=N; i++) head[i] = -1;} }; using namespace Graph; ll K; ll dp[maxN]; void dfs(int u, int fa) {int sum = 0;for(int i=head[u], v; ~i; i=edge[i].nex){v = edge[i].to;if(v == fa) continue;dfs(v, u);sum += dp[v];}dp[u] = 0;for(int i=head[u], v; ~i; i=edge[i].nex){v = edge[i].to;if(v == fa) continue;dp[u] = max(dp[u], sum + du[u] - K);} } bool check(int lim) {K = lim;dfs(1, 0);return dp[1] == 0; } int main() {scanf("%d", &N);init();for(int i=1, u, v; i<N; i++){scanf("%d%d", &u, &v);_add(u, v);}for(int i=2; i<=N; i++) du[i] --;int l = 0, r = N - 1, mid, ans = N - 1;while(l <= r){mid = HalF;if(check(mid)){r = mid - 1;ans = mid;}else{l = mid + 1;}}printf("%d\n", ans);return 0; }

?

總結

以上是生活随笔為你收集整理的[POI2013]LUK-Triumphal arch【树形DP+二分答案】的全部內容，希望文章能夠幫你解決所遇到的問題。

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