清北学堂2022夏图论DP营结业测试题

应 wlw 的要求，本文章重置，但不会添加个人理解与吐槽，仅作为题目摘录。

A - Faker

题目背景

现在站在你面前的是：
$OGN2013$夏季赛冠军、$OGN$夏季赛$MVP$、$S3$世界总决赛冠军 年度$MVP$、$OGN2013-2014$冬季冠军、$OGN2013-2014$冬季赛$MVP....$(此处省略一千字)，大飞老师！！！

题目内容

大飞老师的$LOL$技术十分精湛，不仅可以操控好自己的角色，还可以高速切屏观察队友，查看是否有演员演自己，随着大飞老师的切屏技术愈发炉火纯青，已经可以切屏查看$n$名队友，且大飞老师已经高超到对于任意一名队友，只需要切屏看一次，就可以分辨出是否是演员。
现在大飞老师开了一场排位，与$n$位队友排到了一起，第$i$名队友的$rank$分为$ri$，$rank$分越高的队友越有可能被收买成为演员，所以对于一名还未检查过的队友，大飞老师下次切屏检查此队友的概率为此队友的$rank$分除以场上未检查过的队友的$rank$分之和，大飞老师十分自信，对于已经检查过的队友大飞老师一定不会再次切屏查看，现作为场外$ob$人员，我们知道只有第$1$名队友是真正的演员，求大飞老师期望切屏多少次后，找到真正的演员。

输入格式

大飞老师的$LOL$技术十分精湛，不仅可以操控好自己的角色，还可以高速切屏观察队友，查看是否有演员演自己，随着大飞老师的切屏技术愈发炉火纯青，已经可以切屏查看$n$名队友，且大飞老师已经高超到对于任意一名队友，只需要切屏看一次，就可以分辨出是否是演员。
现在大飞老师开了一场排位，与$n$位队友排到了一起，第$i$名队友的$rank$分为$ri$，$rank$分越高的队友越有可能被收买成为演员，所以对于一名还未检查过的队友，大飞老师下次切屏检查此队友的概率为此队友的$rank$分除以场上未检查过的队友的$rank$分之和，大飞老师十分自信，对于已经检查过的队友大飞老师一定不会再次切屏查看，现作为场外$ob$人员，我们知道只有第$1$名队友是真正的演员，求大飞老师期望切屏多少次后，找到真正的演员。

输出格式

一行一个数，表示切屏次数的期望，保留 3 位小数

样例 1 输入

3
1 1 1
BASIC

样例 1 输出

2.000
APACHE

样例 2 输入

5
1 2 3 2 2
BASIC

样例 2 输出

3.750
APACHE

提示

$对于70\%的数据，n<=10$
$对于另20\%的数据，rank分全为1$
$对于100\%的数据，n<=1e5,1<=ri<=1e9$

时间&空间限制

1000ms，512MB，10 个测试点。

B - Clearlove7

题目背景

对面酒桶在我们野区，他为什么要去塔里啊，下路一直叫我去，我怎么去啊？别人一直进我野区

题目内容

厂长的野区是一棵由$n-1$条边连接起来的一棵树，每条边有一个对应的权值$ci$
厂长准备破釜沉舟连着抓对面下路，可是对面下路不是傻瓜，不会一直停留在一个点等着厂长来抓，而且由于对面酒桶也在野区，所以走的越远厂长的安全性越低
现有$q$个事件依次发生，
事件 1：厂长出发抓对方下路，给出厂长抓人时的起点$x$，对方下路所在点$y$，与厂长初始的安全值 v，厂长沿着树上路径$x->y$依次经过每条边，每走过一条边权为$c$的边，厂长的安全值 v 会变成$\lfloor \frac{v}{c} \rfloor$（注意是每除一次都向下取整,与除完所有数再向下取整有区别），抓人结束时厂长的安全值
事件 2：修改一条边的边权，保证修改后的权值<=原来的边权，且>=1

输入格式

第一行$n,q$表示节点数和事件数
接下来$n-1$每行三个整数$u,v,c$表示$u$与$v$之间有一条边权为$c$的边
加下来$q$行，每行第一个数 type
如果$type=1$，则表示为事件$1$：接下来三个数$x,y,v$意义见题面
如果$type=2$，则表示为事件$2$：接下来两个整数$p,c，$表示将第$p$条边的边权修改为$c$

输出格式

对于每个事件$1$输出一行一个数表示答案

样例 1 输入

6 5
1 2 7
1 3 3
3 4 2
3 5 5
3 6 10
1 4 2 1000
1 5 4 1
2 2 2
1 1 3 4
1 1 3 1000
BASIC

样例 1 输出

23
0
2
500
TEXT

样例 2 输入

10 10
1 2 76059
2 3 76226
2 4 57198
2 5 20245
3 6 98555
2 7 31353
1 8 546
2 9 95267
6 10 82113
2 4 14307
2 1 12834
1 1 9 533922680420084446
1 7 1 29798516785177733
2 6 20974
2 6 12249
1 7 7 893521740049148240
1 7 10 676148128050219735
2 7 388
2 2 71839
BASIC

样例 2 输出

436690601
74054850
893521740049148240
0
DNS

提示

$对于70\%的数据，n,q<=1000$
$对于100\%的数据，n,q<=1e5,1<=v,c_i<=10^{18}$

时间&空间限制

1000ms，512MB，10 个测试点。

C - Uzi

题目背景

我们是对线对线打不过，打团打团打不过，就是纯靠个人实力在玩游戏，这种要怎么打？跟我第一盘打$FNC$一样，那阵容看得我都不知道怎么赢。我当时就很想说的，但我也没说。这个阵容我一看，我知道又要输。我们这英雄选出来都是感觉莫名其妙，就我们玩的好的英雄就选。就这样吧，我感觉就这样

题目内容

$RNG$的教练痛定思痛，决心在以后的比赛中选一个好阵容，现有$n$个英雄连接成一棵树，第$i$个英雄的强度为$val_i$,定义一个好阵容所选的英雄对应到树上一定是一个联通块，阵容的强度为阵容所选的英雄的强度的乘积，在一场比赛$RNG$的队员会迷信$1$个英雄，所以选的阵容一定要包含这个英雄
英雄强度会随着版本更迭而改变。

输入格式

第一行两个整数$n,q$，表示英雄个数和事件个数。
第二行$n$个整数表示$val_{1...n}$，表示英雄强度。
第三行$n-1$个整数表示$2...n$号点的父亲。
接下来$q$行，第一行一个整数$op={0,1}$，
如果$op=0$，接下来两个整数$k,c$，表示版本更迭，第$k$个英雄的强度改为$c$
如果$op=1$，接下来两个整数$k,s$，此次比赛$RNG$队员迷信的英雄为$k$，求所有英雄数量为$s$的好阵容的强度之和，对$10^9+7$取模

输出格式

对于$op=1$，每行一个数表示答案

样例 1 输入

15 14
115183048 241960123 26953737 286981714 559777501 20522615 267077699 633773490 831818232 435625134 893455418 131573295 110436785 756765653 754794526
1 1 3 2 2 2 2 3 8 1 9 7 1 12
0 9 116567292
1 9 10
0 6 94825258
0 5 489125457
1 7 4
1 4 7
1 14 6
0 13 748000088
0 2 799291594
1 2 8
0 7 50976790
0 1 112973583
1 3 6
0 5 148254799
BASIC

样例 1 输出

790288877
32433811
966115862
742959567
64472039
326457686
DNS

提示

测试点$1：n,q<=15$
测试点$2,3：n,q<=5000$
测试点$4,5：n,q<=100000,k=1$
测试点$6,7：n,q<=100000,$每个节点权值始终为$1$，无修改操作
测试点$8,9,10：n,q<=100000$
节点$k$的父亲为$1,2,...,k-1$均匀随机
$val_i\in[0,1e9+7),s<=10$

时间&空间限制

2000ms，512MB，10 个测试点。

D - ly

题目背景

他被整个世界绑架了。
绑架方式与大多数同性质事件一样，他需要承受绑架者的希冀，也需要行使被绑架者的职责。
这看起来是一个荒诞的故事——在芸芸众生中，有四个人被内部钦定了，包括他在内。
他们行使人类史上的最高权力而不需解释，承担人类史上的最高责任而无法推脱。
当世界需要他化解危机而他无能为力时，他被世人嘲讽、鄙夷。
当世界需要他用咒语维持威慑，敬他又畏他时，他必须是那个高明而不食人间烟火的人，一夫当关。
当世界不再需要他时，他便被放逐到偏远寒冷的冥王星了却残生。
何谓责任，为了实现目标，虽千万人吾往矣。
他明明是一个人，还能空对画中人的笑而流泪，却直到最后一刻，仍用自己生命的余火发出微光，照亮永恒之墓，化作不灭之灯。
没有寒锋凝结血液的战栗，没有丰碑镌刻岁月的名字，
到最后，唯有一层扁平而杂乱、直到末路的人类依旧无法解读的，沉默的遗迹。
遗迹…
(训练营中一位同学与小女朋友共度春宵后异常激动，给我发了一段文字，让我一定要将这段文字放在题目背景里让大家赏析，题目名并不是此同学名字的缩写，请大家不要乱猜^-)

题目内容

给定长度为$n$的非负整数序列$a$
求满足以下条件的所有序列$b$的中$ \sum_{i=1}^{n}|a_i-b_i| $的最小值是多少
1、序列所有元素异或和恰好是$0$
2、且序列长度为$n$

输入格式

第一行一个整数$T$,表示数据组数
接下来$2T$行，每两行代表一组测试数据：
$1、$每组测试数据的第一行为一个整数$n$表示序列长度
$2、$接下来一行$n$个非负整数表示序列$a$

输出格式

$T$行，每行一个数表示答案

样例 1 输入

4
3
1 2 3
4
1 1 1 1
4
10 5 6 2
5
123 321 213 312 231
BASIC

样例 1 输出

4
3
1 2 3
4
1 1 1 1
4
10 5 6 2
5
123 321 213 312 231
BASIC

提示

测试点$1： n=2,a_i<=10^9$
测试点$2$~$4： n<=15,a_i<=10^3$
测试点$5$~$8： n<=15,a_i<=10^5$
测试点$9$~$12： n<=8,a_i<=10^9$
测试点$13$~$15： n<=10,a_i<=10^9$
测试点$16$~$17： n<=12,a_i<=10^9$
测试点$18$~$20： n<=15,a_i<=10^9$
对于 $100\%的数据满足T<=6$

时间&空间限制

3000ms，512MB，20 个测试点。