D. Serval and Rooted Tree (樹狀DP)

Codeforce 1153D Serval and Rooted Tree (樹狀DP)

今天我們來看看CF1153D
題目連結

題目
給一棵數，假設有(k)個葉節點，我們可以給葉節點分配(1)~(k)這些數字，當做這些節點的"值"。
每個非葉節點的點(不妨令為點(u))的值有可能是所有(u)的子節點的(min)或(max)。
令根節點為節點(1)，求根節點可能的最大值。

想法

首先有可能想到要做樹狀dp，而每個點的狀態就是:「假設點(u)為根的子樹有(k_u)個葉節點，(dp[u])為(1)~(k_u)中的最大可能(如果我們給這(k_u)個葉節點分配(1)~(k_u)的值)」。
如果點(u)為(min)，那麼我們只要找出(u)的子節點中(dp)值最小的就好。但是如果點(u)為(max)，那麼要得到(dp[u])，我們只需要在『「(dp)值最大的(u)的子節點(令為(v))」的子樹的葉節點』中分配(k_u)中最大的(k_v)個即可。
但是如果這樣做，我們會需要維護每一個節點的子樹總共有多少個葉節點。因此我們不妨把(dp)陣列儲存的東西改為:(dp[u])為(k_u-)((1)~(k_u)中的最大可能)+1，也就是這次是從(k_u)開始往(1)數，看最大值為第幾個數到的。
如此一來，(dp)轉移式即可改為:
(egin{cases} dp[u]=min{dp[v]}_{vin son(u)} ext{if u is max}\ dp[u]=sum_{vin son(u)} dp[v] ext{if u is min} end{cases})
而最終的答案即為(k-dp[1]+1)

程式碼:

const int _n=3e5+10;
int t,n,s[_n],dpT[_n],k;
VI G[_n];
int dp(int v){
  if(dpT[v])return dpT[v];
  if(SZ(G[v])==0){k++;return dpT[v]=1;}
  if(s[v]==1){dpT[v]=dp(G[v][0]);rep(i,1,SZ(G[v]))dpT[v]=min(dpT[v],dp(G[v][i]));}
  if(s[v]==0)rep(i,0,SZ(G[v]))dpT[v]+=dp(G[v][i]);
  return dpT[v];
}
main(void) {cin.tie(0);ios_base::sync_with_stdio(0);
  cin>>n;rep(i,1,n+1)cin>>s[i];
  rep(i,2,n+1){cin>>t;G[t].pb(i);}
  dp(1);cout<<k-dp(1)+1<<'
';
  return 0;
}

標頭、模板請點Submission看
Submission