題目描述

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

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

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

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

輸入輸出格式

輸入格式：

?

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

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

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

?

輸出格式：

?

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

?

輸入輸出樣例

輸入樣例#1：?
10 4 0 2 2 2 4 1 0 4 1 1 3 6 2 3 1 9 1 8 1 1 0 0 2 7 4 0 1 5 0 輸出樣例#1：?
4

說明

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

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

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

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

?

HEOI2015 T1。

一上來的題應(yīng)該不能太難吧，，，，，所以我直接往貪心上想了2333，幸好的確是個貪心題。

我們考慮一個點刪除帶來的影響：(我們設(shè)一個節(jié)點的重量參數(shù) h[i] = son[i] + c[i])

? ? 一個點x被刪除，僅會影響父節(jié)點的重量參數(shù)，且會讓它的重量參數(shù) +=c[x]+son[x]-1，也就是x的重量參數(shù)-1。

所以我們可以先預(yù)處理出所有點的重量參數(shù)，因為上限都是m，所以就可以直接從下向上貪心了。

?

#include<bits/stdc++.h> #define ll long long #define maxn 2000005 using namespace std; int to[maxn],ne[maxn]; int hd[maxn],n,m,c[maxn]; int siz[maxn],num=0,ans;inline int read(){int x=0; char ch=getchar();while(!isdigit(ch)) ch=getchar();for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';return x; }void dfs(int x){ int T=0,a[siz[x]+3];siz[x]+=c[x];for(int i=hd[x];i;i=ne[i]){dfs(to[i]),a[++T]=siz[to[i]];}sort(a+1,a+T+1);for(int i=1;i<=T;i++){if(siz[x]+a[i]-1<=m){siz[x]+=a[i]-1,ans++;}else return;} }int main(){scanf("%d%d",&n,&m);for(int i=0;i<n;i++) c[i]=read();int K,SON;for(int i=0;i<n;i++){siz[i]=K=read();while(K--){SON=read();to[++num]=SON,ne[num]=hd[i],hd[i]=num;}}dfs(0);printf("%d\n",ans);return 0; }

　　

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

總結(jié)

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

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