[CF1208H]Red Blue Tree

本文主要是介绍[CF1208H]Red Blue Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Red Blue Tree

题解

首先可以发现一点，在树的叶子颜色固定的情况下，每个非叶节点的颜色关于$k$是单调的。也就是指在$k$从小变大的过程中，必然是先是蓝色，再某个时间点从蓝变红，然后一直是红色。
这个结论其实是相当容易理解的。
当$k$极小时显然所有非叶节点都是蓝色的，因为它的叶节点无论怎么染色都是不可能比$k$小。
而我们考虑现在让我们的$k$变大，那么显然我们的叶子节点上一层的节点是在从蓝色变成红色的，也就是说它们这一层的红色节点增加，蓝色节点减少，显然变了也不会再变回去。
既然这一层只会有蓝色变红色，那么再上面一层的节点的红儿子增多，也是只会从蓝色变红色，按这样下去，整棵树都是这个趋势。
显然，最后当$k$变得极大的时候，所有非叶节点就都是红色的了。
可以发现，对于每个非叶节点，它都有一个变色的$k$值分界点，我们可以根据这个来判断它在当前$k$值下的颜色。

对于一棵给定的树，$k$值其实是比较好计算的。我们设$k_i$表示点$i$变化的$k$值点。
其必要条件为：
$$\begin{gathered} (\left|so{n}_u\right|-\sum _{v\in so{n}_u}[k_v⩽k_u])-\sum _{v\in so{n}_u}[k_v⩽k_u]<k_u \\ \iff \Delta =k_u-|so{n}_u|+2\sum _{v\in so{n}_u}[k_v⩽k_u]>0 \end{gathered}$$由于我们的$k_u$的取值应该是满足上面条件的所有取值中最小的一个，而所有取值显然是连续的，我们可以考虑通过二分去计算这个取值。
当然，我们是需要维护修改操作的，显然这样的话我们后面一个和式又是一个值域上的前缀和的形式，那么我们就可以想到通过在权值线段树上二分去求出这个$k$值。
我们每次更改只需要在一个节点的值域线段树上修改后，就可以去二分出这个节点的$k$值。

我们修改的是一个叶子节点，当颜色发生变化后我们肯定要修改它的父亲节点，看它的父亲节点是否会发生变化。
这样的话我们会发现一个问题，如果整条链很长，每次修改就可能会让许多节点发生变化，这样的话就可能会$T$飞。
注意，我们每次修改的都是从叶节点到根节点的一条链，这时候就很容易联想到重链剖分了，维护链嘛。
对于轻儿子与父亲之间，我们不妨就直接将轻儿子对父亲的影响直接加到权值线段树上去，毕竟每次更改最多会进行$\log n$次这种操作，先对于父亲节点，将它只含有这些轻儿子的答案算出来。
现在我们考虑，加上一个$k$值为$x$的重儿子会有什么影响。
我们的$k_u$的变化肯定是不会超过$1$的，因为对于原本的$Blue-Red>k_u$的式子左边的变化就不会超过$1$。
当$x>k_u$时，$k_u$肯定不会变小，$k$值是使得$\Delta >0$的最小值，现在$\Delta$中$|so{n}_u|$会增加$1$，其它的不变。所以当$\Delta =1$时，我们的$k_u$

这篇关于[CF1208H]Red Blue Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---