BZOJ 4027 [HEOI 2015] 兔子与樱花解题报告

这个题看起来好神的感觉。实际上也好神。。。

我们可以考虑设 $f_u$ 表示以 $u$ 为根的子树中最多能删多少个点，

再设 $g_u$ 表示以 $u$ 为根的子树中删了 $f_u$ 个点之后，$u$ 的 $son(i) + c_i$ 的最小值。

然后就可以树形 Dp 啦。

转移的话，考虑 $u$ 的孙子及更后辈，有：

$$f_u += sum_{vin {son_u}}f_v$$

然后考虑可以 $u$ 的哪些儿子。

首先删掉一个点 $x$ 的话，会对 $fa_x$ 的载重产生 $g_x - 1$ 点个贡献，

所以我们就按照这个贡献来排序，然后贪心地从小到大来选择是否删掉这个点。

那么我们就能够对 $f_u$ 和 $g_u$ 进行转移了。

时间复杂度 $O(nlog n)$，应该是可以过的吧。。。

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 #define N 2000000 + 5
 8  
 9 int n, m, tot;
10 int C[N], Size[N], Head[N], F[N], G[N], q[N], T[N];
11  
12 struct Edge
13 {
14     int next, node;
15 }h[N];
16  
17 inline void addedge(int u, int v)
18 {
19     h[++ tot].next = Head[u];
20     Head[u] = tot;
21     h[tot].node = v;
22 }
23  
24 inline int getint()
25 {
26     char ch = '
';
27     for (; ch > '9' || ch < '0'; ch = getchar()) ;
28     int res = ch - '0';
29     for (ch = getchar(); ch >= '0' && ch <= '9'; ch = getchar())
30         res = (res << 3) + (res << 1) + ch - '0';
31     return res;
32 }
33  
34 inline void Solve()
35 {
36     int l = 1, r = 1;
37     q[1] = 0;
38     while (l <= r)
39     {
40         int z = q[l ++];
41         for (int i = Head[z]; i; i = h[i].next)
42         {
43             int d = h[i].node;
44             q[++ r] = d;
45         }
46     }
47     for (; r; r --)
48     {
49         int z = q[r];
50         F[z] = T[0] = 0, G[z] = Size[z] + C[z];
51         for (int i = Head[z]; i; i = h[i].next)
52         {
53             int d = h[i].node;
54             F[z] += F[d];
55             T[++ T[0]] = G[d] - 1;
56         }
57         sort(T + 1, T + T[0] + 1);
58         for (int i = 1; i <= T[0]; i ++)
59         {
60             if (G[z] + T[i] <= m)
61                 G[z] += T[i], F[z] ++;
62             else break ;
63         }
64     }
65 }
66  
67 int main()
68 {
69     #ifndef ONLINE_JUDGE
70         freopen("4027.in", "r", stdin);
71         freopen("4027.out", "w", stdout);
72     #endif
73      
74     n = getint(), m = getint();
75     for (int i = 0; i < n; i ++)
76         C[i] = getint();
77     for (int i = 0; i < n; i ++)
78     {
79         Size[i] = getint();
80         for (int j = 1; j <= Size[i]; j ++)
81         {
82             int d = getint();
83             addedge(i, d);
84         }
85     }
86     Solve();
87     printf("%d
", F[0]);
88      
89     #ifndef ONLINE_JUDGE
90         fclose(stdin);
91         fclose(stdout);
92     #endif
93     return 0;
94 }

4027_Gromah

BZOJ 4027 [HEOI 2015] 兔子与樱花 解题报告

BZOJ 4027 [HEOI 2015] 兔子与樱花解题报告