参考《算法竞赛进阶指南》、AcWing题库

贪心

贪心是一种在每次决策时采取当前意义下最优策略的算法, 因此, 使用贪心法要求问题的整体最优性可以由局部最优性导出。贪心算法的正确性需要证明, 常见的证明手段有:

  1. 微扰 (邻项交换)
    证明在任意局面下, 任何对局部最优策略的微小改变都会造成整体结果变差。经常用于以 “排序” 为贪心策略的证明。
  2. 范围缩放
    证明任何对局部最优策略作用范围的扩展都不会造成整体结果变差。
  3. 决策包容性
    证明在任意局面下, 作出局部最优决策以后, 在问题状态空间中的可达集合包含了作出其他任何决策后的可达集合。换言之, 这个局部最优策略提供的可能性包含其他所有策略提供的可能性。
  4. 反证法
  5. 数学归纳法
    我们通过几道例题来介绍贞心算法的应用。

110. 防晒

有 CC 头奶牛进行日光浴，第 ii 头奶牛需要 minSPF[i]minSPF[i] 到 maxSPF[i]maxSPF[i] 单位强度之间的阳光。

每头奶牛在日光浴前必须涂防晒霜，防晒霜有 LL 种，涂上第 ii 种之后，身体接收到的阳光强度就会稳定为 SPF[i]SPF[i]，第 ii 种防晒霜有 cover[i]cover[i] 瓶。

求最多可以满足多少头奶牛进行日光浴。

输入格式

第一行输入整数 CC 和 LL。

接下来的 CC 行，按次序每行输入一头牛的 minSPFminSPF 和 maxSPFmaxSPF 值，即第 ii 行输入 minSPF[i]minSPF[i] 和 maxSPF[i]maxSPF[i]。

再接下来的 LL 行，按次序每行输入一种防晒霜的 SPFSPF 和 covercover 值，即第 ii 行输入 SPF[i]SPF[i] 和 cover[i]cover[i]。

每行的数据之间用空格隔开。

输出格式

输出一个整数，代表最多可以满足奶牛日光浴的奶牛数目。

数据范围

1≤C,L≤25001 \le C,L \le 2500,
1≤minSPF≤maxSPF≤10001 \le minSPF \le maxSPF \le 1000,
1≤SPF≤10001 \le SPF \le 1000

输入样例：

1
2
3
4
5
6
3 2
3 10
2 5
1 5
6 2
4 1

输出样例：

1
2

算法分析

按照 minSPF 递减的顺序把奶牛排序, 依次考虑每头奶牛。

对于每头奶牛, 扫描一遍所有的防晒霜, 在这头奶牛能用 (能用指的是该防晒霜的强度符合这头奶牛的范围, 并且瓶数还有剩余）的防晒霜里找 SPF 值最大的使用。

以上算法的贪心策略是在满足条件的前提下每次选 SPF 最大的防晒霜。这个策略为什么是正确的呢? 我们考虑这一步策略的作用范围扩展到后续其他奶牛之后产生的影响。每瓶防晒霜是否可用, 会被 minSPF 与 maxSPF 两个条件限制。因为奶牛已被按照 minSPF 递减排序, 所以每一个不低于当前奶牛 minSPF 值的防晒霜, 都不会低于后面其他奶牛的 minSPF。也就是说, 对于当前奶牛可用的任意两瓶防晒霜 xx 与 yy, 如 果 SPF⁡[x]<SPF⁡[y]\operatorname{SPF}[x]<\operatorname{SPF}[y], 那么后面其他奶牛只可能出现 “ x,yx, y 都能用” “ x,yx, y 都不能用” 或者 “ xx 能用, yy 不能用” 这三种情况之一。因此当前奶牛选择 maxSPF 较大的 yy 去使用, 对于整体问题的影响显然比选择 maxSPF 较小的 xx 更好。

另外, 每头奶牛对答案的贡献至多是 1。即使让当前这头奶牛放弃日光浴, 留下防晒霜给后面的某一头奶牛用, 对答案的贡献也不会变得更大。综上所述, 尽量满足当前的奶牛, 并选择 SPF 值尽量大的防晒霜是一个正确的贪心策略。

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
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2506;
int n, m;
struct COW {
	int l, r;
	bool operator < (const COW x) const {
		return l > x.l;
	}
} cow[N];
struct SPF {
	int s, c;
	bool operator < (const SPF x) const {
		return s > x.s;
	}
} spf[N];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) scanf("%d %d", &cow[i].l, &cow[i].r);
	for (int i = 1; i <= m; i++) scanf("%d %d", &spf[i].s, &spf[i].c);
	sort(cow + 1, cow + n + 1);
	sort(spf + 1, spf + m + 1);
	int ans = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (spf[j].c && spf[j].s >= cow[i].l && spf[j].s <= cow[i].r) {
				ans++;
				spf[j].c--;
				break;
			}
	cout << ans << endl;
	return 0;
}

Solution

111. 畜栏预定

有 NN 头牛在畜栏中吃草。

每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏。

给定 NN 头牛和每头牛开始吃草的时间 AA 以及结束吃草的时间 BB，每头牛在 [A,B][A,B] 这一时间段内都会一直吃草。

当两头牛的吃草区间存在交集时（包括端点），这两头牛不能被安排在同一个畜栏吃草。

求需要的最小畜栏数目和每头牛对应的畜栏方案。

输入格式

第 11 行：输入一个整数 NN。

第 2..N+12..N+1 行：第 i+1i+1 行输入第 ii 头牛的开始吃草时间 AA 以及结束吃草时间 BB，数之间用空格隔开。

输出格式

第 11 行：输入一个整数，代表所需最小畜栏数。

第 2..N+12..N+1 行：第 i+1i+1 行输入第 ii 头牛被安排到的畜栏编号，编号是从 11 开始的 连续 整数，只要方案合法即可。

数据范围

1≤N≤500001 \le N \le 50000,
1≤A,B≤10000001 \le A,B \le 1000000

输入样例：

1
2
3
4
5
6
5
1 10
2 4
3 6
5 8
4 7

输出样例：

1
2
3
4
5
6
4
1
2
3
2
4

算法分析

按照开始吃草的时间把牛排序。

维护一个数组 SS, 记录当前每个畜栏安排进去的最后一头牛, 最初没有畜栏。依次对于每头牛, 扫描数组 SS, 找到任意一个畜栏, 满足当前的牛开始吃草的时间不早于畜栏中最后一头牛结束吃草的时间。如果这样的畜栏不存在, 则为其新建一个畜栏。

这个贪心算法的时间复杂度是 O(N2)O\left(N^{2}\right), 请读者自行证明其正确性。我们可以用一个小根堆 (STL priority_queue ) 维护每个畜栏最后一头牛结束吃草的时间, 尝试把当前的牛安排在堆顶（结束时间最早）的畜栏中, 时间复杂度可以降低到 O(Nlog⁡N)O(N \log N) 。

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
#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50006;
int n, ans[N];
struct COW {
	int id, l, r, ans;
	bool operator < (const COW x) const {
		return l < x.l;
	}
} cow[N];
priority_queue<pair<int, int> > s;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cow[i].id = i;
		scanf("%d %d", &cow[i].l, &cow[i].r);
	}
	sort(cow + 1, cow + n + 1);
	for (int i = 1; i <= n; i++) {
		int num = s.size();
		if (num && -s.top().first < cow[i].l) {
			cow[i].ans = s.top().second;
			s.pop();
			s.push(make_pair(-cow[i].r, cow[i].ans));
			continue;
		}
		cow[i].ans = ++num;
		s.push(make_pair(-cow[i].r, num));
	}
	cout << s.size() << endl;
	for (int i = 1; i <= n; i++) ans[cow[i].id] = cow[i].ans;
	for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
	return 0;
}

Solution

112. 雷达设备

假设海岸是一条无限长的直线，陆地位于海岸的一侧，海洋位于另外一侧。

每个小岛都位于海洋一侧的某个点上。

雷达装置均位于海岸线上，且雷达的监测范围为 dd，当小岛与某雷达的距离不超过 dd 时，该小岛可以被雷达覆盖。

我们使用笛卡尔坐标系，定义海岸线为 xx 轴，海的一侧在 xx 轴上方，陆地一侧在 xx 轴下方。

现在给出每个小岛的具体坐标以及雷达的检测范围，请你求出能够使所有小岛都被雷达覆盖所需的最小雷达数目。

输入格式

第一行输入两个整数 nn 和 dd，分别代表小岛数目和雷达检测范围。

接下来 nn 行，每行输入两个整数，分别代表小岛的 x，yx，y 轴坐标。

同一行数据之间用空格隔开。

输出格式

输出一个整数，代表所需的最小雷达数目，若没有解决方案则所需数目输出 −1-1。

数据范围

1≤n≤10001 \le n \le 1000,
−1000≤x,y≤1000-1000 \le x,y \le 1000

输入样例：

1
2
3
4
3 2
1 2
-3 1
2 1

输出样例：

1
2

算法分析

对于 xx 轴上方的每个建筑物, 可以计算出 xx 轴上的一段能管辖它的区间 l[i]∼l[i] \sim r[i]r[i] 。问题转化为: 给定 NN 个区间, 在 xx 轴上放置最少的点, 使每个区间包含至少一 个点。

按照每个区间的左端点 l[i]l[i] 从小到大排序, 用一个变量维护已经安放的最后一台监控设备的坐标 pos, 起初 pos 为负无穷。

依次考虑每个区间。如果当前区间 ii 的左端点 l[i]l[i] 大于最后一台监控设备的坐标, 则新增一台设备, 令 pos=r[i]pos =r[i] 。否则就让最后一台已经安放的监控设备来管辖当前区间，并令 pos=min(r[i],pos)pos=min(r[i],pos) 。

依此类推, 直至所有区间被管辖, 输出安放的设备个数即可。

这个贪心算法可以用 “决策包容性” 来证明。

首先, 对于每个区间 l[i]∼r[i]l[i] \sim r[i], 有两种选择:

  1. 使用已有的监控设备管辖它。
  2. 新建一台监控设备管辖它。

我们的贪心策略是, 当选择 1 可行时, 不会选择 2 。选择 1 之后, 未来可以在任意位置新建一台监控设备, 而选择 2 则需要在 l[i]∼r[i]l[i] \sim r[i] 之间新建设备, 也就是说, 第 1 项选择未来可能到达的状态包含了第 2 项选择未来可能到达的状态。

其次, 在选择 1 之后, 我们把上一台设备调整到 min⁡(r[i],pos)\min (r[i], p o s) 的位置, 也就是在能管辖 ii 的前提下尽量往后放, “尽量往后放” 这个策略未来的可达状态显然也包含了 “放在更靠前的位置” 未来的可达状态。最后, 因为所有区间已经按照 l[i]l[i] 排序, 所以这个调整不会影响到已经被管辖的区间, 证毕。

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
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
#define ld long double
using namespace std;
const int N = 1006;
const double INF = -0x3f3f3f3f, eps = 0.000001;
int n, d, num = 0;
struct P {
	int x, y;
	double l, r;
	bool operator < (const P x) const {
		return l < x.l;
	}
} p[N];

void Radar_Installation() {
	for (int i = 1; i <= n; i++) scanf("%d %d", &p[i].x, &p[i].y);
	bool b = 1;
	for (int i = 1; i <= n; i++)
		if (p[i].y > d) {
			b = 0;
			break;
		}
	if (!b) {
		cout << "Case " << ++num << ": -1" << endl;
		return;
	}
	for (int i = 1; i <= n; i++) {
		ld k = sqrt((ld)d * d - (ld)p[i].y * p[i].y);
		p[i].l = p[i].x - k, p[i].r = p[i].x + k;
	}
	sort(p + 1, p + n + 1);
	int ans = 1;
	double pos = -INF;
	for (int i = 1; i <= n; i++) {
		if (pos + eps < p[i].l) {
			ans++;
			pos = p[i].r;
		} else pos = min(p[i].r, pos);
	}
	cout << "Case " << ++num << ": " << ans << endl;
}

int main() {
	while (cin >> n >> d && n && d) Radar_Installation();
	return 0;
}

Solution

114. 国王游戏

恰逢 HH 国国庆，国王邀请 nn 位大臣来玩一个有奖游戏。

首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。

然后，让这 nn 位大臣排成一排，国王站在队伍的最前面。

排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是:

排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。

注意，国王的位置始终在队伍的最前面。

输入格式

第一行包含一个整数 nn，表示大臣的人数。

第二行包含两个整数 aa 和 bb，之间用一个空格隔开，分别表示国王左手和右手上的整数。

接下来 nn 行，每行包含两个整数 aa 和 bb，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。

输出格式

输出只有一行，包含一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

数据范围

1≤n≤10001 \le n \le 1000
0<a,b<100000 < a,b <10000

输入样例：

1
2
3
4
5
3
1 1
2 3
7 4
4 6

输出样例：

1
2

算法分析

按照每个大臣左、右手上的数的乘积从小到大排序, 就是最优排队方案。这个贪心算法可以使用微扰（邻项交换）证明。

对于任意一种顺序, 设 nn 名大臣左、右手上的数分别是 A[1]∼A[n]A[1] \sim A[n] 与 B[1]∼B[n]B[1] \sim B[n], 国王手里的数是 A[0]A[0] 和 B[0]B[0] 。

如果我们交换两个相邻的大臣 ii 与 i+1i+1, 在交换前这两个大臣获得的奖励是:

1B[i]∗∏j=0i−1A[j] 与 1B[i+1]∗∏j=0iA[j]\frac{1}{B[i]} * \prod_{j=0}^{i-1} A[j] \text { 与 } \frac{1}{B[i+1]} * \prod_{j=0}^{i} A[j]

交换之后这两个大臣获得的奖励是:

1B[i+1]∗∏j=0i−1A[j] 与 A[i+1]B[i]∗∏j=0i−1A[j]\frac{1}{B[i+1]} * \prod_{j=0}^{i-1} A[j] \text{ 与 } \frac{A[i+1]}{B[i]} * \prod_{j=0}^{i-1} A[j]

其他大臣获得的奖励显然都不变, 因此我们只需要比较上面两组式子最大值的变 化。提取公因式 ∏j=0i−1A[j]\prod_{j=0}^{i-1} A[j] 后, 实际上需要比较下面两个式子的大小关系:

max⁡(1B[i],A[i]B[i+1])  ,  max⁡(1B[i+1],A[i+1]B[i])\max \left(\frac{1}{B[i]}, \frac{A[i]}{B[i+1]}\right) \;,\;\max \left(\frac{1}{B[i+1]}, \frac{A[i+1]}{B[i]}\right)

两边同时乘上 B[i]∗B[i+1]B[i] * B[i+1], 变为比较:

max⁡(B[i+1],A[i]∗B[i])  ,  max⁡(B[i],A[i+1]∗B[i+1])\max (B[i+1], A[i] * B[i]) \;,\;\max (B[i], A[i+1] * B[i+1])

注意到大臣手上的数都是正整数, 故 B[i+1]≤A[i+1]∗B[i+1]B[i+1] \leq A[i+1] * B[i+1], 且 A[i]∗A[i] * B[i]≥B[i]B[i] \geq B[i] 。

于是, 当 A[i]∗B[i]≤A[i+1]∗B[i+1]A[i] * B[i] \leq A[i+1] * B[i+1] 时, 左式 ≤\leq 右式, 交换前更优。当 A[i]∗B[i]≥A[i+1]∗B[i+1]A[i] * B[i] \geq A[i+1] * B[i+1] 时, 左式 ≥\geq 右式, 交换后更优。也就是说, 在任何局面下, 减小逆序对数都不会造成整体结果变差, 而增加逆序对数则不会使整体结果变好。

最后, 根据冒泡排序的知识, 任何一个序列都能通过邻项交换的方式变为有序序列。故当逆序对数为 0 , 即按上述方案排序时就是最优策略。

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1006;
int n, k[N*4], lk = 1, ans[N*4], la = 1, ans0[N*4], la0 = 1;
struct P {
	int a, b;
	bool operator < (const P x) const {
		return a * b < x.a * x.b;
	}
} p[N];

void gj1(int x) {
	for (int i = 1; i <= lk; i++) k[i] *= x;
	lk += 4;
	for (int i = 1; i <= lk; i++) {
		k[i+1] += k[i] / 10;
		k[i] %= 10;
	}
	while (!k[lk]) lk--;
}

void gj2(int x) {
	int w = 0;
	bool flag = 1;
	for (int i = lk; i; i--) {
		w = w * 10 + k[i];
		ans0[i] = w / x;
		w %= x;
		if (ans0[i] && flag) {
			la0 = i;
			flag = 0;
		}
	}
}

bool pd() {
	if (la != la0) return la < la0;
	for (int i = la; i; i--)
		if (ans[i] != ans0[i]) return ans[i] < ans0[i];
	return 0;
}

int main() {
	cin >> n;
	for (int i = 0; i <= n; i++) scanf("%d %d", &p[i].a, &p[i].b);
	sort(p + 1, p + n + 1);
	memset(k, 0, sizeof(k));
	memset(ans, 0, sizeof(ans));
	memset(ans0, 0, sizeof(ans0));
	k[1] = 1;
	gj1(p[0].a);
	for (int i = 1; i <= n; i++) {
		gj2(p[i].b);
		if (pd()) {
			memcpy(ans, ans0, sizeof(ans));
			la = la0;
		}
		gj1(p[i].a);
	}
	for (int i = la; i; i--) cout << ans[i];
	cout << endl;
	return 0;
}

Solution

115. 给树染色

一颗树有 nn 个节点，这些节点被标号为：1,2,3…n1,2,3…n，每个节点 ii 都有一个权值 A[i]A[i]。

现在要把这棵树的节点全部染色，染色的规则是：

根节点 RR 可以随时被染色；对于其他节点，在被染色之前它的父亲节点必须已经染上了色。

每次染色的代价为 T×A[i]T \times A[i]，其中 TT 代表当前是第几次染色。

求把这棵树染色的最小总代价。

输入格式

第一行包含两个整数 nn 和 RR，分别代表树的节点数以及根节点的序号。

第二行包含 nn 个整数，代表所有节点的权值，第 ii 个数即为第 ii 个节点的权值 A[i]A[i]。

接下来 n−1n-1 行，每行包含两个整数 aa 和 bb，代表两个节点的序号，两节点满足关系： aa 节点是 bb 节点的父节点。

除根节点外的其他 n−1n-1 个节点的父节点和它们本身会在这 n−1n-1 行中表示出来。

同一行内的数用空格隔开。

输出格式

输出一个整数，代表把这棵树染色的最小总代价。

数据范围

1≤n≤10001 \le n \le 1000,
1≤A[i]≤10001 \le A[i] \le 1000

输入样例：

1
2
3
4
5
6
5 1
1 2 1 2 4
1 2
1 3
2 4
3 5

输出样例：

1
33

算法分析

有一个错误的贪心算法是 “每一步在可以被染色的点里选权值最大的染色”, 读者很容易构造出其反例一一只要构造一棵树, 让一个权值很小的节点下边有很多权值巨大的节点, 另一个权值较大的节点却没有子节点。

不过从这个错误的贪心算法的思考中, 我们可以提取出一个正确的性质: 树中除根节点外权值最大的点, 一定会在它的父节点被染色后立即染色。

于是我们可以确定的是, 树中权值最大的点及其父节点的染色操作是连续进行的, 我们可以把这两个点 “合并起来” 。合并得到的新点的权值设为这两个点的权值的平均值。

例如有权值为 x,y,zx, y, z 的三个点, 我们已知 xx 和 yy 的染色操作是连续进行的, 那么就有两种可能的染色方案:

  1. 先染 x,yx, y, 再染 zz, 代价是 x+2y+3zx+2 y+3 z 。
  2. 先染 zz, 再染 x,yx, y, 代价是 z+2x+3yz+2 x+3 y 。

我们主要关心这两个代价之间的大小关系, 所以不妨把两个式子同时加上 (z−y)(z-y) 再除以 2 , 分别得到:

  1. 代价 (x+y)/2+2∗z(x+y) / 2+2 * z 。
  2. 代价 z+2∗((x+y)/2)\mathrm{z}+2 *((x+y) / 2) 。

这恰好就相当于有权值为 (x+y)/2(x+y) / 2 和 zz 的两个点的两种染色次序。换言之, 下列两种情况的 “最优染色次序” 可以互相转化:

  1. 权值为 x,y,zx, y, z 的三个点。
  2. 权值为 (x+y)/2(x+y) / 2 和 zz 的两个点。

进一步推进, 我们可以得到一种 “等效权值” 的算法: 记录每个点是由多少个点合并而成的, 一个点的 “等效权值” 定义为:

该点包含的原始权值总和 ÷ 该点包含的原始点数\text{该点包含的原始权值总和 } \div \text{ 该点包含的原始点数}

根据一开始提到的性质, 我们不断在树中取 “等效权值” 最大的点 pp, 与其父节点 faf a 合并。合并之前 pp 与 faf a 各自包含的点的染色顺序是已知的, 我们就让 pp 中第一个点排在 faf a 中最后一个点之后紧接着被染色, 把这个顺序保存在 pp 与 faf a 合并以后的点上。最终整棵树合并成一个点后, 我们就按照这个点内保存的顺序在原始的树上把各个节点依次染色, 计算出花费的总代价, 即为所求。

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
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1006;
int n, r, fa[N], nxt[N], lst[N], num[N];
double c[N], d[N], tot[N];
bool v[N];

void Color_a_Tree() {
    for (int i = 1; i <= n; i++) {
        scanf("%lf", &c[i]);
        nxt[i] = i;
        lst[i] = i;
        num[i] = 1;
        tot[i] = c[i];
    }
    memcpy(d, c, sizeof(d));
    for (int i = 1; i < n; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        fa[b] = a;
    }
    memset(v, 0, sizeof(v));
    for (int i = 1; i < n; i++) {
        int p;
        double k = 0;
        for (int j = 1; j <= n; j++)
            if (j != r && !v[j] && c[j] > k) {
                k = c[j];
                p = j;
            }
        int f = fa[p];
        while (v[f]) fa[p] = f = fa[f];
        nxt[lst[f]] = p;
        lst[f] = lst[p];
        num[f] += num[p];
        tot[f] += tot[p];
        c[f] = tot[f] / num[f];
        v[p] = 1;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += i * d[r];
        r = nxt[r];
    }
    cout << ans << endl;
}

int main() {
    while (cin >> n >> r && n && r) Color_a_Tree();
    return 0;
}

Solution