隐藏
「Codeforces Round 240 div1」E. Mashmokh's Designed Problem - Dfs序/ETT | Bill Yang's Blog
0%

「Codeforces Round 240 div1」E. Mashmokh's Designed Problem - Dfs序/ETT

题目大意

    一颗有$n$个节点的树,根节点始终为$1$,每个节点的若干个子节点有序。你需要进行$m$次操作,操作分为三种:
1.查询两个节点$u,v$之间的距离,每条边的长度均为$1$。
2.给出一个非根节点$u$,断开$u$与其父亲节点的边,将$u$与第$h$个祖先连上一条边并将$u$作为该祖先的最后一个儿子,$u$的父亲是$u$的第一个祖先。
3.查询从根节点出发进行dfs,深度为$k$的点中最后被遍历到的点的编号,根节点的深度为$0$。


题目分析

这是一棵真正的动态树,注意到儿子的有序关系以及换子树操作,不难想到使用ETT解决本题。

简单介绍一下ETT:
ETT是动态树的另一种算法,通过展开树的欧拉环游序对树的信息进行维护,支持换子树/换根/修改等操作,可以询问子树信息,不能询问链上信息。

详细的见ETT学习笔记(尚未完稿)。

对于本题,操作1实际上是查询两点的LCA,因为欧拉环游序的性质,我们可以查询两点间深度最小的点即为LCA。
操作2是裸的换子树操作。
操作3就有点玄妙了,我们可以通过数据结构(平衡树)上的二分解决这个问题。

注意到询问的满足条件最后一个点,不难想到二分,平衡树维护一个子树深度最大值和最小值,因为欧拉环游序的深度不会突变,因此有单调性,我们可以这样二分:
首先判断右子树是否满足条件(是否有一个满足深度条件的点),若有递归右子树,否则判断当前点是否是要求的点,若是则返回,否则递归左子树。

这样我们就可以解决这个问题了。

再具体实现的时候,我们也可以不使用欧拉环游序,使用非压缩的欧拉括号序同样可以解决,只是查询LCA的时候是最小深度$-1$的点。


代码

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
194
195
196
197
198
199
200
201
202
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
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=200005;

int n,q,First[maxn],Last[maxn],step=2;
vector<int>edges[maxn];

struct Tree {
int child[2],father;
int key,small,big,depth,lazy,id;
Tree() {}
Tree(int l,int r,int fa,int k,int d,int _id):father(fa),key(k),small(d),big(d),depth(d),lazy(0),id(_id) {
child[0]=l;
child[1]=r;
}
};
struct Splay {
int size,root;
Tree tree[maxn];
#define ls(x) tree[x].child[0]
#define rs(x) tree[x].child[1]
#define fa(x) tree[x].father
#define val(x) tree[x].key
#define lazy(x) tree[x].lazy
#define depth(x) tree[x].depth
Splay() {
tree[++size]=Tree(0,2,0,-INT_MAX,0,0);
tree[size].small=INT_MAX,tree[size].big=-INT_MAX;
tree[++size]=Tree(0,0,1,INT_MAX,0,0);
tree[size].small=INT_MAX,tree[size].big=-INT_MAX;
root=size;
}
void clear(int index) {
tree[index]=Tree(0,0,0,0,0,0);
}
bool checkson(int index) {
return rs(fa(index))==index;
}
void modify(int index,int v) {
lazy(index)+=v;
if(index<=2)return;
depth(index)+=v;
tree[index].small+=v;
tree[index].big+=v;
}
void push_down(int index) {
if(!lazy(index))return;
if(ls(index))modify(ls(index),lazy(index));
if(rs(index))modify(rs(index),lazy(index));
lazy(index)=0;
}
void push_up(int index) {
if(!index)return;
if(index<=2)tree[size].small=INT_MAX,tree[size].big=-INT_MAX;
else tree[index].small=tree[index].big=depth(index);
if(ls(index)) {
tree[index].small=min(tree[index].small,tree[ls(index)].small);
tree[index].big=max(tree[index].big,tree[ls(index)].big);
}
if(rs(index)) {
tree[index].small=min(tree[index].small,tree[rs(index)].small);
tree[index].big=max(tree[index].big,tree[rs(index)].big);
}
}
void rotate(int index) {
int father=fa(index),grand=fa(father),side=checkson(index);
if(grand)tree[grand].child[checkson(father)]=index;
tree[father].child[side]=tree[index].child[side^1];
fa(tree[father].child[side])=father;
fa(father)=index;
tree[index].child[side^1]=father;
fa(index)=grand;
push_up(father);
push_up(index);
}
void splay(int index,int target=0) {
push_down(index);
for(int father; (father=fa(index))!=target; rotate(index)) {
int grand=fa(father);
if(grand)push_down(grand);
push_down(father);
push_down(index);
if(fa(father)!=target)rotate(checkson(index)==checkson(father)?father:index);
}
if(target==0)root=index;
}
int insert(int v,int d,int id) {
int now=root,father=0;
while(now&&val(now)!=v) {
father=now;
now=tree[now].child[val(now)<v];
}
tree[now=++size]=Tree(0,0,father,v,d,id);
if(father)tree[father].child[val(father)<v]=now;
splay(now);
return now;
}
int pre_suc(int bj) {
push_down(root);
int now=tree[root].child[bj];
while(tree[now].child[bj^1])push_down(now),now=tree[now].child[bj^1];
push_down(now);
return now;
}
int Find(int index,int d) {
while(true) {
push_down(index);
if(rs(index)&&tree[rs(index)].small<=d&&tree[rs(index)].big>=d)index=rs(index);
else if(tree[index].depth==d)return index;
else index=ls(index);
}
}
int dist(int x,int y) {
if(x==y)return 0;
splay(First[x]);
splay(First[y],root);
int pos=tree[First[y]].child[checkson(First[y])^1];
int ans=pos?tree[pos].small-1:INT_MAX;
ans=min(ans,min(depth(First[x]),depth(First[y])));
return depth(First[x])+depth(First[y])-2*ans;
}
void change(int x,int y) {
splay(First[x]);
int p=tree[Find(ls(First[x]),depth(First[x])-y)].id; //找到目标结点
//分离
int pre=pre_suc(0);
splay(Last[x]);
int suc=pre_suc(1);
splay(pre);
splay(suc,pre);
int pos=ls(suc);
push_down(pre),push_down(suc); //传递残余标记
int num=-depth(pre)-(pre==First[tree[pre].id]); //若是其父亲还要-1
fa(pos)=ls(suc)=0;
push_up(suc),push_up(pre);
//拼接
splay(Last[p]);
pre=pre_suc(0);
splay(pre);
splay(suc=Last[p],pre);
push_down(pre),push_down(suc); //先传递标记,否则会影响新加入的子树
num+=depth(pre)+(pre==First[tree[pre].id]);
ls(suc)=pos;
fa(pos)=suc;
modify(pos,num);
push_up(suc);
push_up(pre);
}
} bbt;

void AddEdge(int x,int y) {
edges[x].push_back(y);
}

void Dfs(int Now,int depth) {
First[Now]=++step;
bbt.insert(step,depth,Now);
for(int Next:edges[Now])Dfs(Next,depth+1);
Last[Now]=++step;
bbt.insert(step,depth,Now);
}

int main() {
n=Get_Int();
q=Get_Int();
for(int i=1; i<=n; i++) {
int x=Get_Int();
while(x--)AddEdge(i,Get_Int());
}
Dfs(1,1);
while(q--) {
int opt=Get_Int(),x=Get_Int();
if(opt==1)printf("%d\n",bbt.dist(x,Get_Int()));
else if(opt==2)bbt.change(x,Get_Int());
else printf("%d\n",bbt.tree[bbt.Find(bbt.root,x+1)].id);
}
return 0;
}
姥爷们赏瓶冰阔落吧~