P3554 LUK-Triumphal arch 解題報告

P3554 [POI2013]LUK-Triumphal arch

題目大意

一顆 $n$ 個點的樹，點有黑白兩種顏色。一開始 1號點是黑色的，A待在 $1$ 號點。重復依次進行以下動作：

選擇 $k$ 個點變成黑色。

A 隨機 向周圍的可直接到達的點走一步。

要使 無論A怎么走，他永遠不會到白點上。求最小的$k$

解題報告

首先，這個 $k$ 顯然是可二分答案的東西。

我們可以考慮樹上dp。dp最核心的一點，就是要尋找到重復子問題。對于樹上dp，就是要在每個子樹中的問題一致化。

有這些顯然的結論：

A往上走不如往下走。往上走相當于耽誤時間，更容易完成任務。

A直接到達的點一定要染色完全。

但是這樣還不夠，不能直接判斷每點的度數。這是因為可能在之前有“多余”的染色，可以提前把一些點染了。我們發現這個東西很難維護。那怎么做？

當然是放進dp狀態里

我們設 $f_i$ 表示把 $i$ 的子樹（不包括 $i$）進行染色，需要“多余染色” 的次數。

有轉移方程 $f_i=\max \{0,\sum _{e(i\to j)}(f_j+1)?k\}$。

這個是很好推的吧。

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; char In[1 << 20], *ss = In, *tt = In; #define getchar() (ss == tt && (tt = (ss = In) + fread(In, 1, 1 << 20, stdin), ss == tt) ? EOF : *ss++) ll read() {ll x = 0, f = 1; char ch = getchar();for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + int(ch - '0');return x * f; } const int MAXN = 3e5 + 5; int n, ver[MAXN << 1], nxt[MAXN << 1], head[MAXN << 1], cnt, k; void addedge(int u, int v) {ver[++cnt] = v; nxt[cnt] = head[u]; head[u] = cnt; } int dfs(int u, int f) {int ans = 0;for(int i = head[u]; i; i = nxt[i]) if(ver[i] != f) {int v = ver[i];ans += (1 + dfs(v, u));}return max(0, ans - k); } int main() {n = read();for(int i = 1; i < n; i++) {int u = read(), v = read();addedge(u, v); addedge(v, u);}int l = 0, r = n-1, ans = -1;while(l <= r) {k = (l + r) >> 1;if(dfs(1, 0) == 0) {ans = k; r = k-1;}else l = k+1;}printf("%d\n", ans);return 0; }

總結

以上是生活随笔為你收集整理的P3554 LUK-Triumphal arch 解题报告的全部內容，希望文章能夠幫你解決所遇到的問題。

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