[ACNOI2022]树上同色连通块
题目
题目背景
“我叫卷爷，职业是
O
U
Y
E
\sf OUYE
OUYE 。就在
3
3
3 月
25
25
25 日那天，我坐在
O
n
e
I
n
D
a
r
k
\sf OneInDark
OneInDark 对面，看到
O
n
e
I
n
D
a
r
k
\sf OneInDark
OneInDark 因为写不完
T
3
T3
T3 正解而愤愤离去。毫无疑问，他就是
A
K
AK
AK 疑案的凶手！”
“「反对」！ O n e I n D a r k \sf OneInDark OneInDark 当时的座位在你的对面，你不可能看到他的举动。你的证词是前后矛盾的！现在想来，能够在无人知晓的情况下悄悄 A K AK AK 的，必须是对学校管理了如指掌的高层，并且还要有充分的内卷能力。所以能够完成这起规模庞大的 A K AK AK 案的人只有一个——”
“ 证人卷爷先生！”
题目描述
给出一棵树，每个点是黑或白色，且有点权。需支持五种操作：改变点的颜色；将某个点所在的同色连通块的点权都增加某个值；询问某个点所在的同色连通块中最大点权；将某条路径上的所有点的点权增加某个值；将某个点的子树内所有点的点权增加某个值。
数据范围与约定
树的大小
n
⩽
2
×
1
0
5
n\leqslant 2\times 10^5
n⩽2×105 且操作数量
q
⩽
2
×
1
0
5
q\leqslant 2\times 10^5
q⩽2×105 。保证答案在
[
0
,
2
31
)
[0,2^{31})
[0,231) 内。
思路
我确实搞不清楚 “树上同色连通块” 的数学原理是什么，就一直往动态 d p \tt dp dp 方向想，然而有链修改我做锤子 😓
仔细想想，对子树进行操作，并且对链进行操作，本来最好的方法就是利用 d f s \rm dfs dfs 序，做树链剖分。如果说能够避免 d f s \rm dfs dfs 序，一般只能依靠永久化标记（比如子树修改）。——故而本题亦存在单 log \log log 做法，请见已被永久判决为 A K AK AK 者的 O U Y E \sf OUYE OUYE 的博客。
但是 d f s \rm dfs dfs 序怎么维护同色连通块？我最初的立论将我推向失败：由于同色连通块变化无穷，我们需要在每个点上记录以它为最高点的同色树上连通块的信息。我未曾考虑过利用 d f s \rm dfs dfs 序来 冲破原有树形结构，愚蠢至极！
可能是对问题的简化比较巧妙吧。首先树上连通块存在最靠近根的点 x x x 。你会发现， y y y 和 x x x 在同一连通块内，当且仅当 y y y 到 x x x 的树链上没有异色点。本来它是对任意 a , b a,b a,b 都成立的；我们将其紧缩到树链的情况，就可以用简单的树上差分来判断！
记 f ( x ) f(x) f(x) 为 x x x 到根节点的路径中，与 x x x 颜色不同的点的数量。则 y y y 隶属于 x x x 的连通块，只需 y y y 与 x x x 同色且 f ( y ) = f ( x ) f(y)=f(x) f(y)=f(x) 。
我们又敏锐地发现， y y y 和 x x x 同色且 y y y 在 x x x 子树中时 f ( y ) ⩾ f ( x ) f(y)\geqslant f(x) f(y)⩾f(x) 。所以，我们只需要查询 x x x 子树中 最小的 f f f 对应的信息！问题迎刃而解！
树链剖分后，对每种颜色开一棵线段树，节点记录 min f \min f minf 以及这样的点的信息。在本题中是 max \max max 点权，当然，它是可以推广到点权和等问题的。那么修改颜色，意味着 f f f 的整体加减；路径修改和子树修改都是普通修改；而修改同色连通块，意味着修改某些区间中的 min f \min f minf 对应的点。显然这样的标记是可合并的。
时间复杂度 O ( n log n + m log 2 n ) \mathcal O(n\log n+m\log^2n) O(nlogn+mlog2n)，瓶颈在于路径修改的 O ( log 2 n ) \mathcal O(\log^2 n) O(log2n) 操作。
代码
理论上，找到自己所在连通块最靠近根的点，可以用全局平衡二叉树做到 O ( log n ) \mathcal O(\log n) O(logn)，但我觉得就算了吧 😂
#include <cstdio> // JZM yydJUNK!!!
#include <iostream> // XJX yyds!!!
#include <algorithm> // XYX yydLONELY!!!
#include <cstring> // DDG yydOLDGOD!!!
#include <cctype> // ZXY yydBUS!!!
typedef long long llong;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
# define rep0(i,a,b) for(int i=(a); i!=(b); ++i)
inline int readint(){
int a = 0, c = getchar(), f = 1;
for(; !isdigit(c); c=getchar()) if(c == '-') f = -f;
for(; isdigit(c); c=getchar()) a = a*10+(c^48);
return a*f;
}
const int MAXN = 200005;
struct Edge{ int to, nxt; };
Edge e[MAXN<<1]; int head[MAXN], cntEdge;
inline void addEdge(int a, int b){
e[cntEdge] = {b,head[a]}, head[a] = cntEdge ++;
e[cntEdge] = {a,head[b]}, head[b] = cntEdge ++;
}
# define _go(i,x) for(int i=head[x]; ~i; i=e[i].nxt)
int fa[MAXN], siz[MAXN], son[MAXN];
void scan(int x, int pre){
siz[x] = 1;
_go(i,x) if((i^1) != pre){
fa[e[i].to] = x, scan(e[i].to,i), siz[x] += siz[e[i].to];
if(siz[e[i].to] > siz[son[x]]) son[x] = e[i].to;
}
}
int dfn[MAXN], dfsClock, top[MAXN], ref[MAXN];
void dfs(int x, const int &bel){
top[x] = bel, ref[dfn[x] = ++ dfsClock] = x;
if(son[x]) dfs(son[x],bel);
_go(i,x) if(e[i].to != fa[x] && e[i].to != son[x])
dfs(e[i].to,e[i].to); // new chain
}
int val[MAXN];
const int INF = 0x3fffffff;
typedef std::pair<int,int> PII;
void operator += (PII &a, const PII &b){
a.first += b.first, a.second += b.second;
}
struct SegmentTree{
PII mx[MAXN*3], adv[MAXN*3];
int ass, dep, tag[MAXN*3];
inline void build(const int &n){
for(ass=1,dep=0; ass<n+2; ass<<=1,++dep);
mx[ass].first = mx[ass+n+1].first = -INF;
rep(i,1,n) mx[ass+i].second = val[ref[i]];
drep(i,ass-1,1) pushUp(i); // build
}
inline void addNode(const int &o, const PII &qv){
mx[o] += qv, adv[o] += qv;
}
inline void tagNode(const int &o, const PII &qv){
if(mx[o].first == qv.first){
mx[o].second += qv.second;
tag[o] += qv.second; // special tag
}
}
inline void pushDown(const int &o){
if(adv[o].first || adv[o].second){
addNode(o<<1,adv[o]);
addNode(o<<1|1,adv[o]), adv[o] = PII{0,0};
}
if(tag[o] != 0){ // reduce constant?
tagNode(o<<1,PII{mx[o].first,tag[o]});
tagNode(o<<1|1,PII{mx[o].first,tag[o]}), tag[o] = 0;
}
}
inline void pushUp(const int &o){
mx[o] = std::max(mx[o<<1],mx[o<<1|1]);
}
inline void add_value(const int &ql, const int &qr, const PII &qv){
int l = ass+ql-1, r = ass+qr+1;
drep(i,dep,1) pushDown(l>>i), pushDown(r>>i);
for(; (l^r)!=1; pushUp(l>>=1),pushUp(r>>=1)){
if(!(l&1)) addNode(l^1,qv);
if(r&1) addNode(r^1,qv);
}
while(l >>= 1) pushUp(l);
}
inline void set_value(const int &qid, const int &qv){
int r = ass+qid; // indice
drep(i,dep,1) pushDown(r>>i);
for(mx[r].second=qv; r>>=1; ) pushUp(r);
}
inline void add_tag(const int &ql, const int &qr, const PII &qv){
int l = ass+ql-1, r = ass+qr+1;
drep(i,dep,1) pushDown(l>>i), pushDown(r>>i);
for(; (l^r)!=1; pushUp(l>>=1),pushUp(r>>=1)){
if(!(l&1)) tagNode(l^1,qv);
if(r&1) tagNode(r^1,qv);
}
while(l >>= 1) pushUp(l);
}
inline PII query(const int &ql, const int &qr){
int l = ass+ql-1, r = ass+qr+1;
drep(i,dep,1) pushDown(l>>i), pushDown(r>>i);
PII res = PII{-INF,0}; // universal
for(; (l^r)!=1; l>>=1,r>>=1){
if(!(l&1)) res = std::max(res,mx[l^1]);
if(r&1) res = std::max(res,mx[r^1]);
}
return res; // no tag remains
}
};
SegmentTree sgt[2];
int n; bool col[MAXN];
namespace fenwick{
int c[MAXN];
inline void modify(const int &qid, const int &qv){
for(int i=n+1-qid; i<=n; i+=(i&-i)) c[i] += qv;
}
inline int _query(const int &qid){
int res = 0; for(int i=qid; i; i&=(i-1))
res += c[i], i &= (i-1), res += c[i];
return res; // two steps a time
}
inline int query(const int &ql, const int &qr){
return _query(n+1-ql)-_query(n-qr);
}
inline int upper_bound(int qr, const bool &f){
qr = n+1-qr; int x = 0, qv;
qv = f ? qr-_query(qr) : _query(qr);
for(int j=17; ~j; --j) if(x+(1<<j) <= n){
int t = f ? (1<<j)-c[x+(1<<j)] : c[x+(1<<j)];
if(t <= qv) x += 1<<j, qv -= t;
}
return n+1-x; // first one in segment
}
}
inline int getLevel(int x){
int res = 0; const bool &f = col[x];
for(int y; x; x=fa[top[x]]){
y = fenwick::query(dfn[top[x]],dfn[x]);
if(f) res += dfn[x]-dfn[top[x]]+1-y; else res += y;
}
return res;
}
inline int findBoss(int x){
for(const bool &tar=col[x]; x; x=fa[top[x]]){
int y = fenwick::upper_bound(dfn[x],tar);
if(dfn[top[x]] < y) return ref[y];
if(col[fa[top[x]]] != tar) return top[x];
}
return 1; // root of the tree
}
inline void switch_color(const int &x){
sgt[col[x]].add_value(dfn[x],dfn[x]+siz[x]-1,PII{-1,0});
val[x] = sgt[col[x]].query(dfn[x],dfn[x]).second;
fenwick::modify(dfn[x], col[x] ? -1 : +1), col[x] ^= 1;
sgt[col[x]].add_value(dfn[x],dfn[x]+siz[x]-1,PII{1,0});
sgt[col[x]].set_value(dfn[x],val[x]); // recalc is needed!
}
inline int query_component(int x){
x = findBoss(x); // statistics on boss
return sgt[col[x]].query(dfn[x],dfn[x]+siz[x]-1).second;
}
inline void add_component(int x, const int &v){
x = findBoss(x); // statistics on boss
int level = -getLevel(x);
return sgt[col[x]].add_tag(dfn[x],
dfn[x]+siz[x]-1,PII{level,v});
}
inline void add_chain(int a, int b, const int &v){
for(; top[a]!=top[b]; a=fa[top[a]]){
if(dfn[top[a]] < dfn[top[b]]) std::swap(a,b);
sgt[0].add_value(dfn[top[a]],dfn[a],PII{0,v});
sgt[1].add_value(dfn[top[a]],dfn[a],PII{0,v});
}
if(dfn[a] > dfn[b]) std::swap(a,b);
sgt[0].add_value(dfn[a],dfn[b],PII{0,v});
sgt[1].add_value(dfn[a],dfn[b],PII{0,v});
}
inline void add_subtree(const int &x, const int &v){
sgt[0].add_value(dfn[x],dfn[x]+siz[x]-1,PII{0,v});
sgt[1].add_value(dfn[x],dfn[x]+siz[x]-1,PII{0,v});
}
int main(){
n = readint(); int q = readint();
memset(head+1,-1,n<<2);
rep0(i,1,n) addEdge(readint(),readint());
scan(1,-1), dfs(1,1); // chain split
rep(i,1,n) if((col[i] = readint()) == true)
fenwick::modify(dfn[i],1); // add
rep(i,1,n) val[i] = readint();
sgt[0].build(n), sgt[1].build(n);
rep(i,1,n) sgt[col[i]^1].add_value(
dfn[i],dfn[i]+siz[i]-1,PII{-1,0});
for(int opt,x,y; q; --q){
opt = readint(), x = readint();
if(opt == 4) y = readint(), add_chain(x,y,readint());
else if(opt == 3) printf("%d\n",query_component(x));
else if(opt == 2) add_component(x,readint());
else if(opt == 5) add_subtree(x,readint());
else if(opt == 1) switch_color(x);
}
return 0;
}