link

CF504E Misha and LCP on Tree

二分哈希判断,用长剖O(1)O(1)kk祖先。单哈希即可,双哈希会T

CF505E Mr. Kitayuta vs. Bamboos

二分答案。按时间倒着操作,操作变为每次把所有物品ai-a_i,选择kk+p+p。每次贪心选最快<0<0的数,用堆维护

CF512D Fox And Travelling

存在两类树:有根树(基环的),无根树

f(i,j)f(i, j)表示ii子树选jj个点的方案,有根树可以直接DP

无根树以每个点为根算一次,数组对应位置相加,再把下标为ii的值除以szisz - i,得到的数组就是这个无根树的方案

xx为根的方案一定是xx点最后选。以该联通块的另一点yy为根时是最后选yy,方案一定不同。

而以该联通块外的szisz - i个点为根时,一定会算xx最后选的方案。

总共被统计了szi+1sz - i + 1

CF516D Drazil and Morning Exercise

先换根DP求出ff数组。根据重心/直径的性质,以直径中点为根时,每个点的ff都比父亲大

每次询问O(n)O(n)做: 按ff从大到小双指针扫,用并查集维护当前合法的点及它的size。涉及到删除操作,但需要删某个点时,他子树内的点一定全都删完了,所以可以直接在并查集里删

CF521D Shop

答案是把所有数相乘,因此所有乘法操作等价

赋值操作只保留最大的,转化成加法操作(注意,转化后和其他加法完全等价

aia_i+k+k操作转化成对答案乘1+kai\displaystyle 1 + \frac{k}{a_i},而对于同一个ii,一定优先选kk更大的。最大的被选上了才有可能选次大的

用堆维护最大的mm个操作

CF521E Cycling City

若某个点双内边数 > 点数,则存在三条不相交路径

输出方案可以先在点双内搜出任意一个环,再从环上找一点,通过不经过环的另一条路径走到环上

CF526F Pudding Monsters

题意即统计maxmin=rl\max - \min = r - l的段数

线段树维护maxmin(rl)\max - \min - (r - l)的最小值及个数。max\maxmin\min不能赋值(否则无法维护最小值个数),用单调栈分别维护

CF526G Spiders Evil Plan

solution

长剖的这个结论又不记得了。。。

CF527E Data Center Drama

构造题真是做不来。。。

首先所有点度数都要是偶数,于是先把度为奇的点两两连一条边,接着如果总边数为奇必然不合法,要随便再连一个自环。

这时就一定存在合法方案了,求出一条欧拉回路,然后把边交叉定向即可,这样每个点都是加一对入边或者一对出边。