「SDOI2017」树点涂色 - LCT均摊分析+线段树 | Bill Yang's Blog

「SDOI2017」树点涂色 - LCT均摊分析+线段树

题目大意

    Bob有一棵$n$个点的有根树,其中$1$号点是根节点。Bob在每个点上涂了颜色,并且每个点上的颜色不同。定义一条路径的权值是:这条路径上的点(包括起点和终点)共有多少种不同的颜色。Bob可能会进行这几种操作:
    $1\,\,x$:
      把点$x$到根节点的路径上所有的点染上一种没有用过的新颜色。
    $2\,\,x\,\,y$:
      求$x$到$y$的路径的权值。
    $3\,\,x$:
      在以$x$为根的子树中选择一个点,使得这个点到根节点的路径权值最大,求最大权值。
    Bob一共会进行$m$次操作。


题目分析

较难的一道题。

我们考虑一种暴力。
用线段树上每一个结点维护其到根的权值,线段树的区间维护最大值。
这样$2,3$询问都可以轻松地解决,考虑如何维护$1$操作。

我们从修改的点$x$一个一个地向上跳到根,对于跳到的每一个结点$i$,维护$i$指出去的每一个点的答案(区间加减)。

显然这样的暴力是$O(nm)$的。

接下来我们考虑,如果树上有连续的一段相同颜色,我们可以直接将这段相同颜色跳过,将路径上的信息全部维护。

这样似乎只是一种暴力的优化方法,但根据均摊分析,它是$O(\log n)$的。

注意到性质:树上的颜色只可能是连续的一段链

这就意味着,每个点只可能往下有一个儿子继承它的颜色,每次对一段区间染色,对每一个点就会发生继承颜色儿子的切换。
是不是很熟悉?没错这就是LCT的虚实边切换,那么答案就是结点到根路径上虚边条数$+1$。
根据LCT的均摊分析,就可以证明这是$O(\log n)$的。

我们用LCT来维护连续的链的跳跃比较好写。
对于每个点进行虚实边切换时,我们找到实儿子(Splay右儿子)子树中深度最浅的点,在线段树中对其子树加$1$,代表颜色切换,其子树到根多了一种颜色。同样的,给虚儿子区间减$1$。

找前驱和线段树操作是$O(\log n)$的,故时间复杂度是$O(m\log^2 n)$。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005;
struct Segment_Tree {
struct Tree {
int left,right;
int max,lazy;
Tree(int l=0,int r=0,int m=0,int la=0):left(l),right(r),max(m),lazy(la) {}
} tree[maxn<<2];
#define ls index<<1
#define rs index<<1|1
void build(int index,int Left,int Right) {
tree[index]=Tree(Left,Right);
if(Left==Right)return;
int mid=(Left+Right)>>1;
build(ls,Left,mid);
build(rs,mid+1,Right);
}
void push_up(int index) {
tree[index].max=max(tree[ls].max,tree[rs].max);
}
void modify(int index,int v) {
tree[index].max+=v;
tree[index].lazy+=v;
}
void push_down(int index) {
if(!tree[index].lazy)return;
modify(ls,tree[index].lazy);
modify(rs,tree[index].lazy);
tree[index].lazy=0;
}
void modify(int index,int Left,int Right,int v) {
if(Left>tree[index].right||Right<tree[index].left)return;
if(Left<=tree[index].left&&Right>=tree[index].right) {
modify(index,v);
return;
}
push_down(index);
modify(ls,Left,Right,v);
modify(rs,Left,Right,v);
push_up(index);
}
int query(int index,int Left,int Right) {
if(Left>tree[index].right||Right<tree[index].left)return 0;
if(Left<=tree[index].left&&Right>=tree[index].right)return tree[index].max;
push_down(index);
return max(query(ls,Left,Right),query(rs,Left,Right));
}
} st;
#undef ls
#undef rs
int First[maxn],Last[maxn];
struct Link_Cut_Tree {
struct Tree {
int father,child[2];
bool rev;
} tree[maxn];
#define fa(x) tree[x].father
#define ls(x) tree[x].child[0]
#define rs(x) tree[x].child[1]
#define rev(x) tree[x].rev
bool isroot(int x) {
return ls(fa(x))!=x&&rs(fa(x))!=x;
}
bool checkson(int x) {
return rs(fa(x))==x;
}
void rotate(int x) {
int father=fa(x),grand=fa(father),side=checkson(x);
if(!isroot(father))tree[grand].child[checkson(father)]=x;
tree[father].child[side]=tree[x].child[side^1];
fa(tree[father].child[side])=father;
fa(father)=x;
tree[x].child[side^1]=father;
fa(x)=grand;
}
void splay(int index) {
for(int father; !isroot(index); rotate(index)) {
father=fa(index);
if(!isroot(father))rotate(checkson(index)==checkson(father)?father:index);
}
}
void access(int index) {
for(int son=0; index; son=index,index=fa(index)) {
splay(index);
if(rs(index)) {
int l=pre(rs(index));
st.modify(1,First[l],Last[l],1);
}
if(son) {
int l=pre(son);
st.modify(1,First[l],Last[l],-1);
}
rs(index)=son;
}
}
int pre(int x) {
while(ls(x))x=ls(x);
return x;
}
} lct;
int n,q,step=0,Depth[maxn],p[maxn][25];
vector<int>edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void Dfs(int Now,int fa,int depth) {
First[Now]=++step;
Depth[Now]=depth;
if(~fa)lct.tree[Now].father=fa;
p[Now][0]=fa;
for(int i=1; i<=20; i++)
if(~p[Now][i-1])p[Now][i]=p[p[Now][i-1]][i-1];
else break;
for(int Next:edges[Now]) {
if(Next==fa)continue;
Dfs(Next,Now,depth+1);
}
Last[Now]=step;
st.modify(1,First[Now],Last[Now],1);
}
int LCA(int x,int y) {
if(Depth[x]<Depth[y])swap(x,y);
int k=20;
for(int i=k; i>=0; i--)
if(Depth[x]-(1<<i)>=Depth[y])x=p[x][i];
if(x==y)return y;
for(int i=k; i>=0; i--)
if(~p[x][i]&&p[x][i]!=p[y][i]) {
x=p[x][i];
y=p[y][i];
}
return p[y][0];
}
int main() {
memset(p,-1,sizeof(p));
n=Get_Int();
q=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
}
st.build(1,1,n);
Dfs(1,-1,1);
while(q--) {
int opt=Get_Int();
if(opt==1)lct.access(Get_Int());
else if(opt==2) {
int x=Get_Int(),y=Get_Int();
int lca=LCA(x,y);
printf("%d\n",st.query(1,First[x],First[x])+st.query(1,First[y],First[y])-2*st.query(1,First[lca],First[lca])+1);
} else {
int x=Get_Int();
printf("%d\n",st.query(1,First[x],Last[x]));
}
}
return 0;
}
本篇文章有用吗?有用还不快点击!
0%