樹形dp [POI 2013] LUK-Triumphal arch
波蘭人神秘題目。
題意
\(n\) 點的樹，初始節(jié)點 1 為黑色，其余白色。
兩個人在博弈。
B 一開始位于 1 點，進行如下的回合。
首先每輪 A 選擇 K 個點，然后 B 選擇一個相鄰的節(jié)點進行移動。
若任意時刻 B 位于白色的節(jié)點則 B 獲勝。
若 A 將點全染黑 A 勝利。
求最小的 K 使得 A 可以獲勝。
\(N\) 是 1e5 級別的。
做法
我上來就寫了一個貪心，后來想想是假的，這里不提了，反正得分還挺高。
這個 K 明顯有單調(diào)性，所以二分 K，嘗試轉(zhuǎn)換為一個判斷問題。
先說結(jié)論，B 不可以走回頭路。
因為 A 自然會堵死每一個 B 到過的節(jié)點，這并沒有任何意義，相當(dāng)于多給了 A 一次染色的機會，完全是愚蠢的。
所以 B 只能一條路走到黑。
A 每一次首先肯定是要先染自己所有的子節(jié)點，如果不夠就需要之前的剩余進行彌補。
發(fā)現(xiàn)這個過程實際上是在合并所有子樹的所需，加上自身的所需向上傳（雖然可能是負數(shù)就對了）。
進而我們考慮樹形 dp。
我們設(shè) dp[u] 表示 u 子樹所需要的之前的染色次數(shù)的總量。
son[u] 表示 u 的子節(jié)點數(shù)量。
不難得出 \(dp[u]=son[u]-k+\sum_{v是u子節(jié)點}^{}max(dp[v],0)\)
注意這里需要取 max, 我一開始并沒有考慮到，因為子樹的次數(shù)是不可能向上貢獻的。
我們只需要檢查 dp[1]<=0 就行的。
時間復(fù)雜度 \(O(nlogn)\)，二分的值域和 n 一樣，不做區(qū)分了。
代碼如下
點擊查看代碼
#include <bits/stdc++.h>
using namespace std;
const int MN=1e6+116;
struct Node{
int nxt, to;
}node[MN];
int head[MN], tottt;
void insert(int u, int v){
node[++tottt].to=v;
node[tottt].nxt=head[u];
head[u]=tottt; return;
}
int n, son[MN], dp[MN], ans;
void Read(){
cin>>n;
for(int i=1,u,v; i<n; ++i){
cin>>u>>v; insert(u,v); insert(v,u);
}
}
void Pre_dfs(int u, int father){
for(int i=head[u];i;i=node[i].nxt){
int v=node[i].to;
if(v==father) continue;
son[u]++; Pre_dfs(v,u);
}
}
void dfs(int u, int father, int k){
dp[u]=son[u]-k;
for(int i=head[u];i;i=node[i].nxt){
int v=node[i].to;
if(v==father) continue;
dfs(v,u,k);
dp[u]+=max(dp[v],0);
}
}
bool judge(int k){
for(int i=1; i<=n; ++i) dp[i]=0;
dfs(1,1,k); return dp[1]<=0;
}
void binary(){
int l=0, r=3000001; ans=3000001;
while(l<=r){
int mid=(l+r)>>1;
if(judge(mid)){
ans=mid; r=mid-1;
}else{
l=mid+1;
}
}
}
void print(){
cout<<ans<<'\n';
}
void solve(){
Read(); Pre_dfs(1,1);
binary(); print();
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
solve();
return 0;
}
浙公網(wǎng)安備 33010602011771號