題目大意
題目描述
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);
// printf("\n%c\n%d\n",s[0],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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/159352.html
標籤：java
上一篇：前端基礎演算法題解法