目录
题目大意题目描述输入格式输出格式：样例样例输入样例输出
题解代码
题目大意
题目描述
Mirko在玩堆栈游戏。开始他有一个空的堆栈，编号为0.在第i步(1<=i<=300000)，他会选择一个编号为v的堆栈，复制一份并做如下操作：
a v 表示将v号堆栈复制一份，新栈的编号为i,并将元素i压入新栈的栈顶。b v 表示将v号堆栈复制一份，新栈的编号为i，将新栈的栈顶元素弹出。c v w 将v号堆栈复制一份，编号为i，并比较第v号和第w号堆栈中有多少相同的数。
输入格式
第一行一个整数n，表示有n步。 接下来n步，每步表示一个操作，如上所述。
输出格式：
对所有的b操作和c操作，输出结果，每行一个。b操作需要输出该栈移除的元素，c操作表示两个堆栈的相同的数的个数。
样例
样例输入
5
a 0
a 1
b 2
c 2 3
b 4
样例输出
2
1
2
题解
对于a类操作，我们可以把i看成是x延伸出去的一个儿子； 对于b类操作，我们可以发现i和x的父节点是等价的，所以我们直接将其在树上的节点设为x的父节点。 对于c类操作，因为每次加入栈中的数互不相同(所有的i都不同)，所以只有在树上经过同一个操作的结点才会增加一个相等的数，即是找LCA。
代码
#include <bits/stdc++.h>
using namespace std
;
const int Step
= 20;
int n
;
int tree
[300005];
bool f
[300005];
int pre
[300005];
int dp
[300005][30];
int tot
[300005];
int First
[300005];
int LCA(int x
, int y
) {
if (pre
[x
] > pre
[y
]) {
int t
= x
;
x
= y
;
y
= t
;
}
for (int i
= Step
; i
>= 0; --i
) {
if (pre
[dp
[y
][i
]] >= pre
[x
])
y
= dp
[y
][i
];
}
if (x
== y
)
return x
;
for (int i
= Step
; i
>= 0; --i
) {
if (dp
[x
][i
] != dp
[y
][i
]) {
x
= dp
[x
][i
];
y
= dp
[y
][i
];
}
}
return dp
[x
][0];
}
int main() {
cin
>> n
;
for (int i
= 1; i
<= n
; i
++) {
char s
[5];
int x
;
scanf("%s%d", s
, &x
);
x
= tree
[x
];
if (s
[0] == 'a') {
tree
[i
] = i
;
dp
[i
][0] = x
;
tot
[i
] = tot
[x
] + 1;
First
[i
] = i
;
pre
[i
] = pre
[dp
[i
][0]] + 1;
for (int j
= 1; j
<= Step
; j
++) {
dp
[i
][j
] = dp
[dp
[i
][j
- 1]][j
- 1];
}
} else if (s
[0] == 'b') {
tree
[i
] = dp
[x
][0];
printf("%d\n", First
[x
]);
} else {
int y
;
scanf("%d", &y
);
y
= tree
[y
];
printf("%d\n", tot
[LCA(x
, y
)]);
tree
[i
] = x
;
}
}
return 0;
}
