NTOJ 1013 [RYOI2018ER]变成

43 阅读 0 评论 29 点赞

我是靠谱客的博主阳光枕头，最近开发中收集的这篇文章主要介绍NTOJ 1013 [RYOI2018ER]变成，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

给定两棵有根树$T_a,T_b$，你可以在$T_a$上进行旋转（就是$splay,treap$那种）

要求把$T_a$转成$T_b$，旋转次数不超过$10^6$

数据保证点数不超过$10^5$

由于是旋转操作，因此并不影响中序遍历结果

也就是说$T_a$和$T_b$的$dfs$序上下标相同的点是配对的

因此只需要在$T_b$上$dfs$，假设当前访问到了$u$，只需要将$u$在$T_a$中的配对点$splay$到$u$所对应的点就行了（之后这个配对点不会再被旋转）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1e5 + 10;
 4 int n, tot, ans[int(1e6) + 10];
 5
 6 inline void read(int &x) {
 7
char c = x = 0;
 8
while(!isdigit(c)) c = getchar();
 9
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
10 }
11
12 struct Tree {
13
int ch[N][2], fa[N], root, dfn[N], pos[N], clk, vis[N];
14
Tree() { vis[0] = 1; }
15
void dfs(int u) {
16
if(ch[u][0]) dfs(ch[u][0]);
17
dfn[pos[u] = ++ clk] = u;
18
if(ch[u][1]) dfs(ch[u][1]);
19 
}
20
inline int rot(int u) {
21 //
cout << "rot in " << u << endl;
22
ans[++ tot] = u;
23
int f = fa[u], g = fa[f];
24
if(g) ch[g][ch[g][1] == f] = u;
25
fa[u] = g;
26
int k = ch[f][1] == u;
27
ch[f][k] = ch[u][!k];
28
if(ch[u][!k]) fa[ch[u][!k]] = f;
29
ch[u][!k] = f, fa[f] = u;
30 
}
31
inline void splay(int u) {
32 //
printf("splay: %dn", u);
33
for(int f = fa[u] ; !vis[f] ; f = fa[u]) {
34 //
printf("fa[%d] = %dn", u, fa[u]);
35
int g = fa[f];
36
if((ch[g][0] == f) == (ch[f][0] == u)) {
37
if(!vis[g]) rot(f);
38
} else {
39 
rot(u);
40 
}
41
if(!vis[fa[u]]) rot(u);
42 
}
43 //
printf("splay endn");
44
vis[u] = 1;
45 
}
46 } xx, mz;
47
48 void dfs(int u) {
49 //
cout << "tot = " << tot << endl;
50
if(!u) return ;
51 
xx.splay(xx.dfn[mz.pos[u]]);
52
dfs(mz.ch[u][0]), dfs(mz.ch[u][1]);
53 }
54
55 int main() {
56 //
freopen("data.in", "r", stdin);
57 //
freopen("data.out", "w", stdout);
58
freopen("become.in", "r", stdin);
59
freopen("become.out", "w", stdout);
60 
read(n);
61
for(int i = 1 ; i <= n ; ++ i) {
62
read(xx.ch[i][0]), read(xx.ch[i][1]);
63
if(xx.ch[i][0]) xx.fa[xx.ch[i][0]] = i;
64
if(xx.ch[i][1]) xx.fa[xx.ch[i][1]] = i;
65 
}
66
for(int i = 1 ; i <= n ; ++ i) {
67
read(mz.ch[i][0]), read(mz.ch[i][1]);
68
if(mz.ch[i][0]) mz.fa[mz.ch[i][0]] = i;
69
if(mz.ch[i][1]) mz.fa[mz.ch[i][1]] = i;
70 
}
71
for(int i = 1 ; i <= n ; ++ i) {
72
if(!xx.fa[i]) xx.root = i;
73
if(!mz.fa[i]) mz.root = i;
74 
}
75
xx.dfs(xx.root), mz.dfs(mz.root), dfs(mz.root), printf("%dn", tot);
76
for(int i = 1 ; i <= tot ; ++ i) printf("%dn", ans[i]);
77 }