A¶

阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有 \(N\) 家住户，第 \(i\) 家住户到入口的距离为 \(S_i\) 米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的 \(X\) 家住户推销产品，然后再原路走出去。

阿明每走 \(1\) 米就会积累 \(1\) 点疲劳值，向第 \(i\) 家住户推销产品会积累 \(A_i\) 点疲劳值。阿明是工作狂，他想知道，对于不同的 \(X\)，在不走多余的路的前提下，他最多可以积累多少点疲劳值。

cin >> n;
F(i, 1, n) cin >> s[i];
F(i, 1, n) cin >> a[i];

F(i, 1, n) cout << ans[i];

5
1 2 3 4 5
1 2 3 4 5

15
19
22
24
25

5
1 2 2 4 5
5 4 3 4 1

12
17
21
24
27

B¶

恰逢 H 国国庆，国王邀请 \(n\) 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 \(n\) 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

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

cin >> n;
cin >> a >> b;
F(i, 1, n) cin >> x >> y

cout << ans

3 
1 1 
2 3 
7 4 
4 6 

2

C¶

皇后有 \(n\) 位大臣，每位大臣的左右手上面分别写上了一个正整数。恰逢国庆节来临，皇后决定为 \(n\) 位大臣颁发奖金，其中第 \(i\) 位大臣所获得的奖金数目为第 \(i - 1\) 位大臣所获得奖金数目与前 \(i\) 位大臣左手上的数的和的较大值再加上第 \(i\) 位大臣右手上的数。

形式化地讲：我们设第 \(i\) 位大臣左手上的正整数为 \(a_i\)，右手上的正整数为 \(b_i\)，则第 \(i\) 位大臣获得的奖金数目为 \(c_i\) 可以表达为：

当然，吝啬的皇后并不希望太多的奖金被发给大臣，所以她想请你来重新安排一下队伍的顺序，使得获得奖金最多的大臣，所获奖金数目尽可能的少。

注意：重新安排队伍并不意味着一定要打乱顺序，我们允许不改变任何一位大臣的位置。

cin >> T;
cin >> n;
F(i, 1, n) cin >> a[i] >> b[i];

F(i, 1, t) cout << ans[i];

1
3
4 1
2 2
1 2

8

2
5
85 100
95 99
76 87
60 97
79 85
12
9 68
18 45
52 61
39 83
63 67
45 99
52 54
82 100
23 54
99 94
63 100
52 68

528
902

D¶

扶苏从深冬的梅岭走出，来到了一棵有 \(n\) 个节点的有根树上。

如果你不知道什么是树，可以认为树是一个边数恰好比节点个数少一的简单无向连通图。

如果我们规定 \(x\) 是树 \(T\) 的根，那么定义任意一个节点 \(y\) 到根的路径就是从 \(y\) 出发不重复经过节点到达 \(x\) 所经过的所经过的点构成的点集。可以证明这样的点集有且仅有一个。

定义一个节点 \(u\) 是节点 \(v\) 的孩子，当且仅当 \(u\) 与 \(v\) 相连且 \(u\) 不在 \(v\) 到根的路径中。如果 \(u\) 是 \(v\) 的孩子，那么定义 \(v\) 是 \(u\) 的家长节点。

如果我是 @_rqy 那种毒瘤神仙的话，可能会问你每个节点的孩子数不超过 \(k\) 的 \(n\) 个节点的带标号无根树一共有多少个，可惜这个问题我也不会，所以我不会问你这么毒瘤的问题。

扶苏从这棵 \(n\) 个节点的树的 \(1\) 号节点出发，沿着树上的边行走。当然我们规定 \(1\) 号节点是这棵树的根。他所行走的规定是：当扶苏在节点 \(u\) 时，扶苏要么在 \(u\) 的孩子中选择一个没有到达过的节点 \(v\) 并行走到 \(v\)，要么选择回到 \(u\) 的家长节点。

现在给每个节点一个权值 \(w\)，其中 \(i\) 号节点的权值为 \(w_i\)。他想给这棵树的某个节点放上从梅岭带出的梅花。我们规定扶苏能在节点 \(u\) 放上梅花当且仅当满足如下条件：

扶苏当前在节点 \(u\)。

对于 \(u\) 的所有孩子 \(v\)，节点 \(v\) 被放上了 \(w_v\) 朵梅花。

同时，扶苏可以在任意时刻收回任意节点上的梅花，在收回梅花时不需要走到对应节点。

现在扶苏想问问你，对于每个节点，如果他想在 \(i\) 号节点上放 \(w_i\) 朵梅花，那么他最少要从梅岭带出多少朵梅花。

cin >> n;
F(i, 1, n-1) cin >> p[i];
F(i, 1, n) cin >> w[i];

F(i, 1, n) cout << ans[i];

提示¶

• \(n\) 的末位数字可以帮助你快速的判断测试点所具有的的特殊性质。

3 
1 2 
1 1 1

2 2 1

3
1 1
1 1 1

3 1 1

6
1 1 2 3 4
3 14 1 5 12 15

21 20 13 20 12 15

A B C D