Tree(树上倍增+LCT)

描述

传送门:2018 Multi-University Training Contest 7 - Problem I

Alice and Bob are playing with a magic tree This magic tree has $n$ nodes,with $n-1$ magic paths connecting them into a connected block. Node $1$ is at the top of the magic tree (layer $0$). Node $i$ is at the $k$th layer, where $k$ is the distance from the node $i$ to the node $1$. Alice and Bob give a mana value on each node. If a magic stone falls on node $i$, it will be sent up to the $k$ layer and appear on the $k$th ancestor node of the $i$ layer($k$ is the mana value of node $i$). This node will continue to send up it, and so on. If the layer of node $i$ is less than $k$, this stone will be sent out of the magic tree. Alice is curious, she will modify the magic value of a node, and ask Bob: If you drop a magic stone on the node $x$, how many times does it take to transfer it out of the magic tree?

Input

Input contains multiple tests
The first line contains one integer $T$($T≤4$), indicating the number of test cases.
The following lines describe all the test cases
For each test case: The first line contains an integer $n$($n≤100000$), indicating the size of the magic tree.
The second line has $n-1$ numbers, and the $i$th number represents the father of the node $i+1$.
The third row has n numbers, and the $i$th number represents the initial mana $a_i$($a_i≤n$) value of each node.
In the fourth line, a number $m$($m≤100000$) represents the number of operations.
The next $m$ lines, one operation per line.
First a number $op$($1≤op≤2$) represents the type of operation.
If $op==1$, a number $x$ will be read immediately, indicating that a magic stone is thrown to the node $x$.
If $op==2$, it will immediately read in two numbers $x$ and $\text{new_a}$, indicating that the magic value of node $x$ is modified to $\text{new_a}$($\text{new_a}≤n$).

Output

For each query with $op==1$, output the answer

Sample Input

1
2
3
4
5
6
7
8
1
4
1 2 3
1 1 1 1
3
1 4
2 3 2
1 4

Sample Output

1
2
4
3

Hint

For the first query: 4->3->2->1->out
For the second query:4->3->1->out

思路

  • 大佬说这是道LCT的傻逼题,好像的确是这样……
  • 每个点向上跳若干步跳到的位置可以使用倍增来查询。
  • 如果每个点向能一次跳到的点(加一个点表示树外)连边,则也构成了一棵树。
  • 由于要修改一个点能跳的步数,即换父亲,询问链上的距离,所以用LCT维护即可。

代码

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1 << 17;
struct LCT
{
int val[maxn], sum[maxn];
int rev[maxn], ch[maxn][2], fa[maxn];
int stk[maxn];
inline void init(int n)
{
for (int i = 1; i <= n; i++)
val[i] = 1, fa[i] = 0, rev[i] = 0, ch[i][0] = ch[i][1] = 0;
}
inline bool isroot(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }
inline bool get(int x) { return ch[fa[x]][1] == x; }
void pushdown(int x)
{
if (!rev[x]) return;
swap(ch[x][0], ch[x][1]);
if (ch[x][0]) rev[ch[x][0]] ^= 1;
if (ch[x][1]) rev[ch[x][1]] ^= 1;
rev[x] ^= 1;
}
void pushup(int x) { sum[x] = val[x] + sum[ch[x][0]] + sum[ch[x][1]]; }
void rotate(int x)
{
int y = fa[x], z = fa[fa[x]], d = get(x);
if (!isroot(y)) ch[z][get(y)] = x;
fa[x] = z;
ch[y][d] = ch[x][d ^ 1], fa[ch[y][d]] = y;
ch[x][d ^ 1] = y, fa[y] = x;
pushup(y), pushup(x);
}
void splay(int x)
{
int top = 0;
stk[++top] = x;
for (int i = x; !isroot(i); i = fa[i]) stk[++top] = fa[i];
for (int i = top; i; i--) pushdown(stk[i]);
for (int f; !isroot(x); rotate(x))
if (!isroot(f = fa[x])) rotate(get(x) == get(f) ? f : x);
}
void access(int x)
{
for (int y = 0; x; y = x, x = fa[x]) splay(x), ch[x][1] = y, pushup(x);
}
int find(int x)
{
access(x), splay(x);
while (ch[x][0]) x = ch[x][0];
return x;
}
void makeroot(int x) { access(x), splay(x), rev[x] ^= 1; }
void link(int x, int y) { makeroot(x), fa[x] = y, splay(x); }
void cut(int x, int y) { makeroot(x), access(y), splay(y), fa[x] = ch[y][0] = 0; }
void update(int x, int v) { val[x] = v, access(x), splay(x); }
int query(int x, int y)
{
makeroot(y), access(x), splay(x);
return sum[x];
}
} lct;

int fa[20][maxn];
int val[maxn];

int kth(int x, int k)
{
for (int i = 16; ~i; i--)
if (k >> i & 1) x = fa[i][x];
return x;
}

int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int n;
scanf("%d", &n);
for (int i = 2; i <= n; i++) scanf("%d", &fa[0][i]);
fa[0][1] = fa[0][n + 1] = n + 1;
lct.init(n + 1);
for (int i = 1; i < 17; i++)
for (int j = 1; j < n + 2; j++) fa[i][j] = fa[i - 1][fa[i - 1][j]];
for (int i = 1, x; i <= n; i++)
{
scanf("%d", &x);
val[i] = kth(i, x);
lct.link(i, val[i]);
}
int q;
scanf("%d", &q);
while (q--)
{
static int op, x, y;
scanf("%d", &op);
if (op == 1)
{
scanf("%d", &x);
printf("%d\n", lct.query(x, n + 1) - 1);
}
else
{
scanf("%d%d", &x, &y);
lct.cut(x, val[x]);
val[x] = kth(x, y);
lct.link(x, val[x]);
}
}
}
}
捐助作者
0%