1208 H. Red Blud Tree

题意:
给定一棵树和常数\(k\),每个结点的颜色为蓝色或红色,叶子结点颜色是给定的,内部结点的颜色为蓝色当且仅当蓝色儿子数\(-\)红色儿子数\(\geq k\).要求支持三种查询:
1.输出某个结点的颜色.
2.修改某个叶子结点的颜色
3.修改\(k\)的值.
题解:
先考虑没有操作2的情况.那么相当于查询某个结点在\(k\)为某个值的时候的颜色.当\(k=-\infty\)时,所有内部结点都为蓝色.对每个内部结点,当\(k\)增大到某个值之后,它会变为红色,并且随着\(k\)增大会一直保持红色.如果算出这个分界点\(k_v=\min\{k':\text{v is red when }k = k'\}\),那么可以\(O(1)\)完成每个查询.可以通过二分从儿子的\(k\)值转移到父亲.复杂度是\(O(n\log n+q)\)(注意\(k\)值范围可以被限定在\([-n,n]\)).
现在考虑修改,暴力修改复杂度会变成\(O(qn\log n)\).对询问进行分块,利用树压缩的方法复杂度会变成\(O((n+q)\sqrt q\log^2n)\).询问块内出现的点称为关键点,具体的操作是对于没有关键点的子树只保留一个\(k\)值,对于每个关键点,可以往上压缩路径,计算出它在两种颜色的情况下传给最近祖先关键点的\(k\)值是多少.将每个关键点的已经确定\(k\)值的儿子(即该儿子及子树都没有关键点)存储在一个vector里并排序,并且存储那些压缩过的路径,同样二分\(k\)值会有一个对数复杂度,在vector里面二分找到第一个大于\(k\)的位置也会有一个对数复杂度,因此复杂度中带有\(log^2n\).实际上,通过对块内询问进一步离线可以去掉\(log^2n\).下面代码复杂度是\(O((n+q)\sqrt q\log^2n)\),足够通过时间限制.
代码