Luogu P4107 [HEOI2015] 兔子与樱花

题目链接：传送门

对于每个点来说，它的权重分为两部分，一部分是子树大小，一部分是自身的点权。很明显是要从叶子节点开始删除，因为只有从下往上处理我们才能知道这个点子树的所有情况。一个点的点权是不会消失的，只会转移到自己的上层节点上，所以说要想删除更多的节点，就要在$m$的限制内按权值从小到大删除子节点。
在输入就可以时处理好每个点的权重，也就是$w[i]=siz[i]+c[i]$。之后从叶子节点开始向上删除。遍历一个点$fr$的所有子节点$i$，将它们按权重从小到大排序，对每个子节点$i$，判断$w[fr]-1+w[i]<=m$，也就是是否可以删除这个子节点，从小到大排序能保证删除最多的子节点，若上式成立，则删除子节点$i$，并更新$fr$的权值$w[fr]$（少了一个子节点，权值的增加量为$w[i]$，总变化量为$w[i]-1$）。

保存子节点可以用优先队列或者开数组实现，使用优先队列会$T$最后一个点，可以写个快读或者开$O_2$。

/*
* @Author: lyle
* @Date:   2023-10-03 11:25:46
* @Last Modified by:   lyle
* @Last Modified time: 2023-10-03 16:30:01
*/

#include 
#define A 2000010

using namespace std;
char Getchar() {
    static char buf[100010], *p1 = buf, *p2 = buf;
    return p1 == p2 and (p2 = (p1 = buf) + fread(buf, 1, 100010, stdin), p1 == p2) ? EOF : *p1++;
}
template<class T> void read(T &x) {
    bool flag = 0; x = 0; char ch = Getchar();
    while (!isdigit(ch)) flag |= ch == '-', ch = Getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = Getchar();
    x = flag ? -x : x;
}
struct node {int next, to;}e[A];
int head[A], num;
void add(int fr, int to) {
	e[++num].next = head[fr];
	e[num].to = to;
	head[fr] = num;
}
int n, m, c[A], k, x;
int siz[A], ans, sum[A];
priority_queue<int, vector<int>, greater<int> > q;
void dfs(int fr) {
	for (int i = head[fr]; i; i = e[i].next) {
		int ca = e[i].to;
		dfs(ca);
	}
	q = priority_queue<int, vector<int>, greater<int> > ();
	for (int i = head[fr]; i; i = e[i].next) {
		int ca = e[i].to;
		q.push(sum[ca]);
	}
	while (!q.empty()) {
		int now = q.top(); q.pop();
		if (sum[fr] - 1 + now <= m) {
			sum[fr] += (now - 1);
			ans++;
		}
		else break;
	}
}

int main(int argc, char const *argv[]) {
	read(n); read(m);
	for (int i = 1; i <= n; i++) read(c[i]);
	for (int i = 1; i <= n; i++) {
		read(k);
		siz[i] = k;
		sum[i] = siz[i] + c[i];
		while (k--) {
			read(x);
			add(i, x + 1);
		}
	}
	dfs(1);
	cout << ans << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

这个题目中需要每次把优先队列清空，由于优先队列没有内置的$clear()$函数，所以我们只能自己来实现清空队列。具体可以选择不断弹出元素，也可以选择给优先队列重新赋值。

while (!q.empty()) q.pop();

q = priority_queue<int> ();
1
2
3