题目大意
维护一棵树，支持如下操作：
- $Q\,d_i$，查询$d_i$到根的权值和
- $C\,x_i\,y_i$，将$x_i$的父亲换为$y_i$
- $F\,p_i\,q_i$，将$p_i$的子树权值加上$q_i$
题目分析
如果没有第二个换父亲操作，本题就是很简单的树链剖分。
因为有这个换父亲操作，不难想到使用ETT维护。
考虑如何用ETT维护结点到根的权值和，我们可以使用括号序，每个结点的左括号权值为正，右括号权值为负，做一次前缀和即可得到答案。
代码
调了很久的原因是没有考虑初始权值为$0$。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
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL 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,a[maxn],First[maxn],Last[maxn],step=2;
struct Tree {
int child[2],father,size;
int key,bj;
LL val,sum,lazy;
Tree() {}
Tree(int l,int r,int fa,int k,LL s,LL v,int _bj):father(fa),key(k),size(s),val(v),sum(v),lazy(0),bj(_bj) {
child[0]=l;
child[1]=r;
}
};
struct Splay {
int size,root;
Tree tree[maxn];
Splay() {
tree[++size]=Tree(0,2,0,-INT_MAX,0,0,0);
tree[++size]=Tree(0,0,1,INT_MAX,0,0,0);
root=size;
}
bool checkson(int index) {
return rs(fa(index))==index;
}
void modify(int index,LL v) {
lazy(index)+=v;
val(index)+=tree[index].bj*v;
sum(index)+=v*size(index);
}
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;
sum(index)=val(index);
size(index)=tree[index].bj;
if(ls(index))sum(index)+=sum(ls(index)),size(index)+=size(ls(index));
if(rs(index))sum(index)+=sum(rs(index)),size(index)+=size(rs(index));
}
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 k,LL v,int bj) {
int now=root,father=0;
while(now) {
father=now;
now=tree[now].child[key(now)<k];
}
tree[now=++size]=Tree(0,0,father,k,bj,v,bj);
if(father)tree[father].child[key(father)<k]=now;
splay(now);
return now;
}
int pre_suc(bool 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 pre_suc(int index,bool bj) {
splay(index);
return pre_suc(bj);
}
int split(int Left,int Right) {
int pre=pre_suc(Left,0),suc=pre_suc(Right,1);
splay(pre);
splay(suc,pre);
push_down(pre),push_down(suc);
return ls(suc);
}
int cut(int x) { //将x子树分离
int pos=split(First[x],Last[x]),father=fa(pos);
ls(father)=fa(pos)=0;
push_up(father),push_up(fa(father));
return pos;
}
void link(int x,int y) { //将x子树拼接到结点y的最后面
int pre=pre_suc(Last[y],0),suc=Last[y];
splay(pre);
splay(suc,pre);
push_down(pre),push_down(suc);
ls(suc)=x;
fa(x)=suc;
push_up(suc),push_up(pre);
}
void add(int x,LL v) { //给x子树增加v
int pos=split(First[x],Last[x]),father=fa(pos);
modify(pos,v);
push_up(father),push_up(fa(father));
}
LL query(int x) { //询问x到根的和
int pos=split(First[1],First[x]);
return sum(pos);
}
} bbt;
vector<int>edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void Dfs(int Now) {
First[Now]=++step;
bbt.insert(step,a[Now],1);
for(int Next:edges[Now])Dfs(Next);
Last[Now]=++step;
bbt.insert(step,-a[Now],-1);
}
int main() {
n=Get_Int();
for(int i=2; i<=n; i++)AddEdge(Get_Int(),i);
for(int i=1; i<=n; i++)a[i]=Get_Int();
Dfs(1);
q=Get_Int();
while(q--) {
char opt=' ';
while(!isalpha(opt))opt=getchar();
int x=Get_Int();
if(opt=='Q')printf("%lld\n",bbt.query(x));
else if(opt=='C') {
int pos=bbt.cut(x);
bbt.link(pos,Get_Int());
} else if(opt=='F')bbt.add(x,Get_Int());
}
return 0;
}
