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

T1 猴子吃香蕉
二分一下次数，然后用简单数学推导一下就知道这个猴子吃了多久了
注意的事项：
二分的时候两个2e9加起来会爆掉int的如果二分上界设成2e9，那么中间运算有可能爆炸
发现如果这个猴子吃的时间会增长，那么二分的上界是O( sqrt( t ) )级别的
于是特判这里就可以了~

T2 点权和
考虑每次修改的贡献

考虑这次操作x造成的影响：
x对自己的贡献：
x的节点值会加上deg[x]+1，deg为度数
x对上方的贡献：
x的父亲节点的值会加上2
x的父亲的父亲节点的值会加上1
x的父亲节点的儿子值会加上1
x对下方的贡献：
x的儿子节点值会加上2
x的儿子的儿子节点值会加上1
对于每个节点x维护几个标记：
tag[x]:x***作的次数
anstag[x]:从子树贡献上来的贡献
sontag[x]:x的儿子***作的总次数
修改的时候：
首先anstag[x] += deg[x]+1
然后对父亲：anstag[ fa[x] ] += 2
然后对父亲的父亲：anstag[ fa[ fa[x] ]++
然后x***作了一次，所以tag[x]++
然后x作为fa[x]的儿子，有：sontag[ fa[x] ]++
查询的时候：
首先ans = anstag[x]
然后x的父亲每次操作对x有2的贡献：
所以ans += tag[ fa[x] ] * 2
x的父亲的父亲每次操作对x有1的贡献：
所以ans += tag[ fa[ fa[x] ] ]
再考虑到x的父亲的其他儿子对于x的贡献：
ans += sontag[ fa[x] ] - tag[x]
因为要去掉x自己的值
这样维护就可以了
总复杂度O( n + m )

T3 手铐
本来是出到仙人掌上的
然后就变成码农特判题了
我们考虑把环给缩掉，缩了之后的点叫做方点，然后本来树上的点叫做圆点

变成

然后想想怎么用这个新图来算答案
首先手铐两端都必须是一个方点
然后可以发现如果一条两端都是方点的路径上总共有x个方点，则这两个端点可以构成2^(x-2)个手铐（每次可以走两端）


如图这构成了4个手铐
考虑对于生成的这个树树形DP
用f[x]表示以x为根的子树，到x构成的“一半的手铐”的数量
也就是说这样的：

DP到这个点的时候，可以把子树中两个“半手铐”在这个点的位置拼起来

半手铐维护的方法就是
f[x] = sigma( f[ son[x] ] );
如果x是圆点，则f[x]不变
如果x是方点，则f[x] = f[x] * 2 + 1
因为下面上来的每个半手铐都可以走两个方向，然后这个点也可以作为一个半手铐的端点
然后合并答案的时候跑个树形DP就可以了
也要分当前的点是圆点还是方点讨论一下
总时间复杂度：O( n )

T4 世界上最可爱的珂朵莉
是个送分题
（然而似乎某个大佬想了10分钟……我感觉她在假我）
考虑贪心
分两步贪心：
首先肯定是把最小的x个人改成y（如果最小的x个人里面有比y大的，肯定是不变的）
然后肯定是从小到大，把第i小的人和第i小的***配对
于是直接贪心配对就可以了
O( nlogn )

T5 珂学送分2
先用2^(2a)的复杂度算出来每个长度为a的01数（也就是长度为a的状压值）对应选择的额外贡献值
比如说我们枚举到这样一个状态：
01001110
a=8 意义就是如果一个长度为a的连续子区间，如果第2，5，6，7个位置都被选择了，这个会有多少额外贡献的加分 比如如果有规则： 第2，5个位置同时选择，会加x分 第5，6，7个位置同时选择，会加y分 第2，3个位置同时选择，会加z分 则这个长度为a的连续区间的额外贡献是x+y 我们定义二进制状态压缩后的状态s的额外贡献是value[s]，然后序列第i个位置的值是A[i] 考虑DP f[i][j][s]表示前i个位置里面选了j个位置，然后最后a个序列中的位置的状压是s 意义就是如果第x个位置被选了而且x >= i – a + 1 则s中第(i-x+1)位就是1
否则是0
这样就可以按照这个状压的状态来算出DP时转移的贡献了 方程是： f[i+1][j][t] , f[i][j][s] + ( i + 1 >= a ? value[t] : 0 ) f[i+1][j + 1][t | 1] , f[i][j][s] + A[i + 1] + ( i + 1 >= a ? value[t | 1] : 0 ) 这样预处理的复杂度：4^a或者2^ab
DP的复杂度：nm2^a
空间复杂度：2^a + nm2^a
然后
发现瓶颈在空间和预处理
预处理的时候可以用枚举子集的方法
预处理复杂度变为3^a
枚举子集是这样实现的：

这样每个t是s的二进制子集，而且总复杂度为3^a
时间复杂度变为：
O( 3^a +nm2^a )
然后用滚动数组优化DP，空间复杂度变为
O( 2^a + m * 2^a )
可以通过此题
注意这个题有一些细节问题要注意……

T6 我永远喜欢珂朵莉
树链剖分，然后问题转换为在DFS序上：
链就是logn次区间加
子树就是1次区间加
最后查询有多少点值>= t
这个可以用一个set维护（线段树和BIT也可以，就按set讲）
set维护的是值相同的连续段
然后每次区间加，就从set里面把这段提取出来，+1，然后放回去，同时维护出现次数>= t的点个数
用其他数据结构维护方法类似，就不讲了
复杂度O( alog^2n + blogn )？
按照常数写法不同，分数分布在64到88分
88 -> 100分做法：
还是树链剖分
想想怎么不用数据结构维护这个东西
可以先想想差分

但是我们肯定不能每次操作都暴力扫这个差分数组，会TLE的
所以我们考虑离散化
可以发现本来所有数都是一样的
进行了一次区间加之后，被加的那个区间和没被加的数值不一样了
考虑差分后前缀加，会变成什么样的效果：
区间[l,r]加 -> 前缀[1,r]加，前缀[1,l-1]减
这个操作会导致第l-1个数与第l-2个数不一样
也会导致第r个数与第r-1个数不一样
但是不会对其他的数造成影响
也就是说区间加只会影响两个端点上的数，而区间中，或者区间外的点中，原本与相邻的点值一样的点还是与其相邻的点值一样
这个其实就是一个类似离散化的东西
于是离散化之后扫一遍就可以得到每段相同区间里面的值了（其实就是说我们把每段值一定相同的区间一起求了，而不是对于每个数组位置分别求）
于是每次把所有差分后的前缀修改拿来排序离散化就可以了
时间复杂度O( alog^2n + blogn )不变，然而常数小了很多
可能可以通过100分的数据

由于这个题排序的数值域只有n=100000
所以我们可以离线，对每次操作的数一起排序
然后不用快速排序，而使用计数排序或者基数排序
这样时间复杂度变为O( alogn + b )
可以通过100分的数据

还有个做法是建立一个虚树然后在上面DFS或者DP一下
如果还是用离线基数排序的方法
复杂度为O( a + b )
可以通过100分的数据

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