【SDOI2017】树点涂色

Source and Judge

SDOI2017
Loj2001

Analysis

请先思考后再展开

一眼LCT的access实现操作1,同一个splay的颜色相同,一个点到根的权值记为val=向上跳的轻边个数

仔细考虑access的过程,x所在的splay,左孩子会作为新splay的一部分且val=1,右孩子则与x间建立一条轻边,所以可以找到右孩子那条链的链顶然后在线段树上dfs序区间+1

然后新的splay那条链的val都是1,所以我第一想法是再上个树剖,反正怎么做都是log方

其实可以稍微动动脑子,每次把y(这条链上x的孩子)所在子树-1,这样到最后val都是1,线段树就能少维护标记了

于是写起来就是很真实的线段树板子+LCT板子

1
2
3
4
5
6
7
8
9
10
11
12
void access(int now)
{
int lst=0;
while(now)
{
if(lst) {while(p[lst].son[0]) lst=p[lst].son[0];splay(lst);SGT::ad(dfn[lst],dfn[lst]+siz[lst]-1,-1);}
splay(now);int t=p[now].son[1];
p[now].son[1]=lst;if(lst) p[lst].fa=now;
if(t) {while(p[t].son[0])t=p[t].son[0];splay(t);SGT::ad(dfn[t],dfn[t]+siz[t]-1,1);}
lst=now;now=p[now].fa;
}
}

完整code

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/31df.html
转载请注明出处,谢谢!