Description

很久很久之前，森林里住著一群兔子。有一天，兔子們突然決定要去看櫻花。兔子們所在森林里的櫻花樹很特殊。櫻花樹由 \(n\) 個(gè)樹枝分叉點(diǎn)組成，編號從 \(0\) 到 \(n-1\)，這 \(n\) 個(gè)分叉點(diǎn)由 \(n-1\) 個(gè)樹枝連接，我們可以把它看成一個(gè)有根樹結(jié)構(gòu)，其中 \(0\) 號節(jié)點(diǎn)是根節(jié)點(diǎn)。這個(gè)樹的每個(gè)節(jié)點(diǎn)上都會有一些櫻花，其中第 \(i\) 個(gè)節(jié)點(diǎn)有 \(c_i\) 朵櫻花。櫻花樹的每一個(gè)節(jié)點(diǎn)都有最大的載重 \(m\)，對于每一個(gè)節(jié)點(diǎn) \(i\)，它的兒子節(jié)點(diǎn)的個(gè)數(shù)和 \(i\) 節(jié)點(diǎn)上櫻花個(gè)數(shù)之和不能超過 \(m\)，即 \(son(i) + c_i \leq m\)，其中 \(son(i)\) 表示 \(i\) 的兒子的個(gè)數(shù)，如果 \(i\) 為葉子節(jié)點(diǎn)，則 \(son(i) = 0\)

現(xiàn)在兔子們覺得櫻花樹上節(jié)點(diǎn)太多，希望去掉一些節(jié)點(diǎn)。當(dāng)一個(gè)節(jié)點(diǎn)被去掉之后，這個(gè)節(jié)點(diǎn)上的櫻花和它的兒子節(jié)點(diǎn)都被連到刪掉節(jié)點(diǎn)的父節(jié)點(diǎn)上。如果父節(jié)點(diǎn)也被刪除，那么就會繼續(xù)向上連接，直到第一個(gè)沒有被刪除的節(jié)點(diǎn)為止。

現(xiàn)在兔子們希望計(jì)算在不違背最大載重的情況下，最多能刪除多少節(jié)點(diǎn)。

注意根節(jié)點(diǎn)不能被刪除，被刪除的節(jié)點(diǎn)不被計(jì)入載重。

Input

第一行輸入兩個(gè)正整數(shù)，\(n\) 和 \(m\) 分別表示節(jié)點(diǎn)個(gè)數(shù)和最大載重

第二行 \(n\) 個(gè)整數(shù) \(c_i\) ，表示第 \(i\) 個(gè)節(jié)點(diǎn)上的櫻花個(gè)數(shù)

接下來 \(n\) 行，每行第一個(gè)數(shù) \(k_i\) 表示這個(gè)節(jié)點(diǎn)的兒子個(gè)數(shù)，接下來 \(k_i\)個(gè)整數(shù)表示這個(gè)節(jié)點(diǎn)兒子的編號

Output

一行一個(gè)整數(shù)，表示最多能刪除多少節(jié)點(diǎn)。

Hint

對于 \(30\%\) 的數(shù)據(jù)，\(1\leq n\leq 5000, 1\leq m\leq 100, 0\leq c_i\leq 100\)

對于 \(70\%\) 的數(shù)據(jù)，\(1\leq n\leq 200000, 1\leq m\leq 2000, 0\leq c_i\leq 1000\)

對于 \(100\%\) 的數(shù)據(jù)，\(1\leq n\leq 2000000, 1\leq m\leq 100000, 0\leq c_i\leq 1000\)

數(shù)據(jù)保證初始時(shí)，每個(gè)節(jié)點(diǎn)櫻花數(shù)與兒子節(jié)點(diǎn)個(gè)數(shù)之和大于 \(0\) 且不超過 \(m\)

Solution

做法：自底向上，貪心的優(yōu)先刪除每個(gè)點(diǎn)的兒子中代價(jià)最小的一個(gè)。

貪心：以 \(sons[i]+c[i]\) 為 \(i\) 點(diǎn)的代價(jià)，每個(gè)點(diǎn)我們選取代價(jià)最小的刪除，結(jié)果一定不會變差。

證明：對于 \(i\) 點(diǎn)和 \(i\) 的兩個(gè)兒子 \(j,p\)，假設(shè) \(c[j]+sons[j]<c[p]+sons[p]\)，由決策包容性，選 \(j\) 優(yōu)先刪除一定比選 \(p\) 優(yōu)先刪除更優(yōu)。

自底向上：從根節(jié)點(diǎn) \(dfs\) ，從葉子結(jié)點(diǎn)向上回溯。路上如果遇到能刪除的點(diǎn)就刪，不必考慮其祖先。

證明：設(shè)點(diǎn) \(i\) 的兒子是 \(j\) ，\(j\) 的兄弟是 \(p\) ，\(j\) 還有一個(gè)兒子是 \(q\)。

\(dfs\) 的過程中，如果在回溯到 \(j\) 的時(shí)候發(fā)現(xiàn)可以刪除 \(q\)，那么就刪除 \(q\)，并更新 \(j\) 本身的代價(jià)，這樣可能會導(dǎo)致無法再回溯到 \(i\) 點(diǎn)的時(shí)候刪除 \(p\)。

粗略想一下這不是有后效性嘛，但是因?yàn)樨澬膭h了兒子而導(dǎo)致這個(gè)點(diǎn)不能再刪，那么我們只會損失一個(gè)點(diǎn)，就是該點(diǎn)，而刪除兒子至少會刪除一個(gè)，所以不會虧。。

綜上，自底向上的刪除無后效性，滿足貪心性質(zhì)。

Code

#include<map> #include<cstdio> #include<cctype> #include<algorithm> #define N 2000005int n,m; int ans; int c[N]; int sons[N],cnt; int tot[N],l[N],r[N];inline char nc(){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 nc getchar inline int getint(){char ch;int res=0;while(!isdigit(ch=nc()));while(isdigit(ch)){res=(res<<1)+(res<<3)+(ch^48);ch=nc();}return res; }bool cmp(int a,int b){return sons[a]+c[a]<sons[b]+c[b]; }void dfs(int now){if(!sons[now]) return;for(int i=l[now];i<=r[now];i++)dfs(tot[i]);std::sort(tot+l[now],tot+r[now]+1,cmp);for(int i=l[now];i<=r[now];i++){if(c[tot[i]]+sons[tot[i]]+c[now]+sons[now]-1<=m){ans++;c[now]+=c[tot[i]];sons[now]+=sons[tot[i]]-1;}else break;} }signed main(){n=getint(),m=getint();for(int i=1;i<=n;i++)c[i]=getint();for(int i=1;i<=n;i++){sons[i]=getint();l[i]=cnt+1;r[i]=cnt+sons[i];for(int j=1;j<=sons[i];j++){int a=getint()+1;tot[++cnt]=a;}}dfs(1);printf("%d\n",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YoungNeal/p/9084704.html

總結(jié)

以上是生活随笔為你收集整理的[HEOI2015] 兔子与樱花的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。