(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）

T1 骰子的游戏

T2 购物

T3 随机树

T4 珂朵莉的无向图
30分做法：暴力
60分做法：随便给的部分分，感觉可以根号分治什么什么的吧
100分做法：每次把一堆点加进去BFS即可
复杂度O( a + mq )

T5 珂朵莉的数列
10分做法：puts( “0” );
30分做法：直接暴力
60分做法：优化暴力
70分做法：
考虑计算贡献，如果有i a[j]的点对( i , j )则会在1 <= l <= i , j <= r <= n的子区间[l,r]中出现，则对答案的贡献是i * ( n - j + 1 )所以用树状数组维护或者分治（归并排序）即可，做法和求普通逆序对差不多
80->100分做法：
发现答案是O( n^4 )级别冷静分析出题人会不会卡爆long long。发现随机数据答案是O( n^4 )级别，放弃吧，还是写高精度吧。
根据常数不等，80分->100分

T6 珂朵莉喊你一声大佬
8分做法：暴力
28分做法：一条链，直接二分答案然后check一下
52分做法：一个环，直接二分答案然后check一下
60分做法：一个菊花图，直接二分答案然后check一下
88->100分做法：
这是一个环套树森林，直接二分答案
然后从叶子向上递推
令b[i] = a[i] - ans
如果b[i] < 0 , 则b[ fa[i] ] += b[i]
否则b[ fa[i] ] 不变
然后把点全部转到环上之后再在环上搞一波
或者可以环缩掉然后乱搞
O( nlogv )，根据常数分数从88分到100分不等
100分做法：
DFS常数很大
我们预处理出这个环套树的拓扑序，然后扫一遍来递推
这样就不会被卡常数了

其他疑问可加以下交流群（加入一个即可啦~）
牛客多校算法训练营1：453799454
牛客全国算法训练营2：330766563
牛客多校算法训练营3：934889305