Description

Foreseeable和拿破侖的御用建筑師讓·夏格倫在玩游戲

讓·夏格倫會玩一個叫“凱旋門”的游戲：現在有一棵n個節點的樹，表示一個國家 1號點代表這個國家的首都 這個游戲由兩個人一起玩 一個玩家扮演視察國家的國王，另一個扮演建立凱旋門的建筑師 一開始只有首都有凱旋門 國王每次會從當前所在城市移動到一個相 鄰的城市 在國王每次移動前，建筑師可以選擇國家內任意不超過k個城市建造出凱旋門 如果在任意一個時刻，國王所在的城市沒有凱旋門 那么國王會很生氣， 扮演建筑師的玩家就輸了 如果所有的城市都建立起了凱旋門而國王一直沒有走到有凱旋門的城市，那么建筑師就勝利了 Foreseeable不會建筑，所以他扮演國王 而讓·夏格倫則 “扮演”建筑師（他本來就是建筑師不需要扮演） 容易發現k的大小非常影響游戲有趣度…… 如果k太大，那么建筑師可以在國王行動前就在所有城市建出凱旋門，那么國王就沒有勝利的希望了 ，這樣Foreseeable會掀桌不玩 如果k太小，那么Foreseeable很有可能會發揮自己所剩無幾的智商走到一個沒有凱旋門的地方 讓·夏格倫想享受虐Foreseeable的快感 所以你要幫他確 定最小的k，使得在這個游戲中，如果建筑師足夠聰明的話，建筑師必勝 Input 第一行一個整數n 接下來n-1行，每行兩個整數u,v，表示u,v相鄰 Output 一行一個整數表示最小的k Sample Input 7 1 2 1 3 2 5 2 6 7 2 4 1Sample Output3 Hint 1<=n<=300000 樣例解釋：在foreseeable第一次行動前，讓在2,3,4城市建好 凱旋門，然后接下來無論foreseeable走到哪個城市， 在5,6,7建好凱旋門就能保證讓的勝利了

---

答案滿足單調性顯然可以二分答案，但是二分完之后該如何呢？
直接模擬顯然不行...然后就被卡住了。
看了題解。
要跑路的人一定是從根跑到葉子節點，不會回頭，因為往回走不但不會逃離，反而會讓另一個人染更多的格子，因為他從根節點到這的路徑一定都被染過色了。
這為樹形DP提供了基礎。
我們設 $f[i]$ 為以i為根的子樹，要讓B不會走到不被染色的節點的子樹的最小需要被覆蓋數量。
顯然 $f[x]=min \left ( \sum_{y\subseteq son[x]} { } f[y] + deg[x] - mid, 0 \right )$ .
$deg[x]$ 為x節點的度數-1(因為不包括他父親)。
然后最后判斷$f[0]$是否等于0就行了。

---

? #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <map> using namespace std; #define reg register inline char gc() {static const int BS = 1 << 22;static unsigned char Buf[BS], *st, *ed;if (st == ed) ed = Buf + fread(st = Buf, 1, BS, stdin);return st == ed ? EOF : *st++; } #define gc getchar inline int read() {int res=0;char ch=getchar();bool fu=0;while(!isdigit(ch)) {if(ch=='-')fu=1;ch=getchar();}while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48), ch=getchar();return fu?-res:res; } #define N 300005 int n; struct edge {int nxt, to; }ed[N*2]; int head[N], cnt, deg[N]; inline void add(int x, int y) {ed[++cnt] = (edge){head[x], y};head[x] = cnt;deg[y]++; } int f[N];int mid;void dp(int x, int fa) {int res = 0;for (reg int i = head[x] ; i ; i = ed[i].nxt){int to = ed[i].to;if (to == fa) continue;dp(to, x);res += f[to] + 1;}f[x] = max(res - mid, 0); }inline bool check() {memset(f, 0, sizeof f);dp(1, 0);return f[1] == 0; }int main() {n = read();for (reg int i = 1 ; i < n ; i ++){int x = read(), y = read();add(x, y), add(y, x);}if (n == 1) return puts("0"), 0;int l = 1, r = n, ans;while(l <= r){mid = l + r >> 1;if (check()) ans = mid, r = mid - 1;else l = mid + 1;}cout << ans << endl;return 0; }

?

轉載于:https://www.cnblogs.com/BriMon/p/9697790.html

總結

以上是生活随笔為你收集整理的[Luogu3554] Poi2013 Triumphal arch的全部內容，希望文章能夠幫你解決所遇到的問題。

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