[推销博客](https://foreverlasting1202.github.io/2019/08/27/CF1208%E9%A2%98%E8%A7%A3/)
### H Red Blue Tree
题意：有一个$n$个节点的树，每个叶子上都有一个固定的颜色（红或蓝），对于非叶子的点，它的颜色是由它儿子们的颜色确定的。若它儿子的蓝色数$-$红色数大于等于一个固定的值$k$，则它也是蓝色的。现有三种操作：
一、询问一个点$x$的颜色。
二、将叶子$x$的颜色改成$c$。
三、将$k$改成$h$。
$1\leq n,Q\leq 10^5,-10^5\leq k\leq 10^5$。
做法：注意到一件事，随着$k$的递增，红的个数不降，可以发现在树的形态固定的情况下，每个点是否变红是有一个确界$k$。考虑如何去维护这个确界$k$。可以发现对于一个点的确界$k$可以从它儿子继承下来，即假设它儿子的确界分别为$k_1,k_2,...,k_m$，它的确界大于等于$k$当且仅当$m-2\ast \sum_{i=1,k_i<=k}^m 1>=k$。这个东西如果暴力做，则可以每次利用平衡树维护儿子信息然后暴力跳$k$。但如果这里暴力做了，那变色操作就不好办了，因为你要重新维护该叶子到根的路径上所有的确界$k$，但理性感觉一下，平衡树里一次只变化了一个点，$k$大概不会跳很多次，然而这个界我并不会估，感觉一下是$O(1)$的，这样就可以保证每次更新一个点的确界$k$的复杂度是$O(logn)$了。所以现在的问题所在就是如何维护暴力跳父亲这个操作。
一般遇到这种情况，有个显然的想法就是类似$DDP$的思路重链剖分，只维护轻儿子的信息，重儿子单独考虑。于是我们发现这道题也可以这样做。一个结点维护的平衡树里只包含轻儿子，一条重链则利用线段树去维护这条重链和它的平衡树上的信息（这里的信息是什么可以自己考虑一下）。这样的话你每次更新的复杂度就降到了$O(log^3n)$（一个$log$是跳重链，一个$log$是线段树单点修改，一个$log$是更新确界$k$），查询是$O(logn)$的。总复杂度是$O(nlog^3n)$。
code（代码看的$Benq$的，用了$pbds$减少码量，注意一些细节）:
```cpp
//2019.8.28 by ljz
//email
[email protected]
//if you find any bug in my code
//please tell me
#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f
#define unl __int128
#define eps 5.6e-8
#define RG register
#define db double
#define pc(x) __builtin_popcount(x)
//#define pc(x) __builtin_popcountll(x)
typedef pair<int,int> Pair;
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pb push_back
#define ull unsigned LL
#define gc getchar
template <class T>using Tree=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
//inline char gc() {
// static char buf[100000],*p1,*p2;
// return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
//}
//inline int read() {
// res s=0,ch=gc();
// while(ch<'0'||ch>'9')ch=gc();
// while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
// return s;
//}
inline int read() {
res s=0,ch=gc(),w=1;
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=gc();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
return s*w;
}
//inline LL Read() {
// RG LL s=0;
// res ch=gc();
// while(ch<'0'||ch>'9')ch=gc();
// while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
// return s;
//}
//inline LL Read() {
// RG LL s=0;
// res ch=gc(),w=1;
// while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=gc();}
// while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
// return s*w;
//}
//inline void write(RG unl x){
// if(x>10)write(x/10);
// putchar(int(x%10)+'0');
//}
inline void swap(res &x,res &y) {
x^=y^=x^=y;
}
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//clock_t start=clock();
//inline void ck(){
// if(1.0*(clock()-start)/CLOCKS_PER_SEC>0.1)exit(0);
//}
const int N=2e5+10;
namespace MAIN{
int n,k;
vector<int> G[N];
int col[N],sz[N],du[N],fa[N],son[N],top[N],dfn[N],idx,pos[N],low[N];
Pair tr[N<<2];
inline Pair operator + (const RG Pair &x,const RG Pair &y){
return mp(min(x.se,max(x.fi,y.fi)),min(x.se,max(x.fi,y.se)));
}
Tree<Pair> T[N];
decltype(begin(T[0])) D[N];
inline int rankget(const RG Tree<Pair> &A,const res &x){
return A.order_of_key(mp(x,inf));
}
inline bool ck(const res &x,const res &val,const RG bool &fl){
res r=rankget(T[x],val)+fl,b=int(T[x].size())+1-r;
return b-r<val;
}
inline void change(const res &x,res &val,const RG bool &fl){
while(ck(x,val-1,fl))val--;
while(!ck(x,val,fl))val++;
}
void modify(res rt,res l,res r,const res &p){
if(l==r){
res x=pos[l];
if(du[x]==1&&x!=1)tr[rt]=(col[x]?mp(inf,inf):mp(-inf,-inf));
else change(x,tr[rt].fi,1),change(x,tr[rt].se,0);
return;
}
res mid=(l+r)>>1;
if(p<=mid)modify(rt<<1,l,mid,p);
else modify(rt<<1|1,mid+1,r,p);
tr[rt]=tr[rt<<1]+tr[rt<<1|1];
}
Pair query(res rt,res l,res r,const res &L,const res &R){
if(L<=l&&r<=R)return tr[rt];
res mid=(l+r)>>1;
if(L<=mid&&R>mid)return query(rt<<1,l,mid,L,R)+query(rt<<1|1,mid+1,r,L,R);
if(L<=mid)return query(rt<<1,l,mid,L,R);
return query(rt<<1|1,mid+1,r,L,R);
}
void dfs(res x,res fax){
sz[x]=1;
for(auto tox:G[x]){
if(tox==fax)continue;
dfs(tox,x),sz[x]+=sz[tox];
if(sz[tox]>sz[son[x]])son[x]=tox;
}
}
void dfs(res x,res fax,res topx){
fa[x]=fax,top[x]=topx,dfn[x]=++idx,pos[idx]=x;
if(son[x])dfs(son[x],x,topx),low[x]=low[son[x]];
else low[x]=dfn[x];
for(auto tox:G[x]){
if(tox==fa[x]||tox==son[x])continue;
dfs(tox,x,tox),D[tox]=T[x].insert(mp(query(1,1,n,dfn[tox],low[tox]).fi,x)).fi;
}
modify(1,1,n,dfn[x]);
}
inline void MAIN(){
n=read(),k=read();
for(res i=1;i<n;i++){
res u=read(),v=read();
G[u].pb(v),G[v].pb(u),du[u]++,du[v]++;
}
for(res i=1;i<=n;i++)col[i]=read();
dfs(1,0),dfs(1,0,1);
res Q=read();
while(Q--){
res opt=read();
if(opt==1){
res x=read();
puts(k>=query(1,1,n,dfn[x],low[x]).fi?"0":"1");
}
else if(opt==2){
res x=read(),c=read();
col[x]=c;
while(233){
modify(1,1,n,dfn[x]),x=top[x];
if(x==1)break;
res Fa=fa[x];
T[Fa].erase(D[x]),D[x]=T[Fa].insert(mp(query(1,1,n,dfn[x],low[x]).fi,x)).fi,x=Fa;
}
}
else k=read();
}
}
}
int main(){
// srand(19260817);
// freopen("signin.in","r",stdin);
// freopen("signin.out","w",stdout);
MAIN::MAIN();
return 0;
}
```