BZOJ

BZOJ 3786

传送门

用$\texttt{Splay}$维护$\texttt{DFS}$序

首先，每个节点到根路径的权值和即为$\texttt{DFS}$序的前缀和

然后对$\texttt{DFS}$序中每个节点存一下权值、进栈或出栈，拿这个建棵$\texttt{Splay}$，求前缀和时直接$\texttt{Splay}$到根然后求$\texttt{Sum}$

坑的地方在于对于一个点是进栈的点还是出栈的点的判断…这个有两种方法，一种是每个点存个布尔变量判断一下，还有就是存个$-1$或$1$的数与权值相乘 显然第二种比第一种不知道高到哪里去了

第一种方法需要进栈加出栈减，第二种方法只用直接加就行，结果拿第二种方法写的时候脑子抽了也搞成了进栈加出栈减…调了好久TAT

还有就是注意int64

卡时拿了PASCAL的一血2333


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
190
191
192
193
194
195
196
197
198
199
200
201
202
203
program bzoj_3786;
var s:array[0..200002]of record fa,lc,rc,f,size,cnt,k,plus:longint; sum:int64; end;
    seq,id:array[1..200002]of longint;
    lst,w,pl,pr:array[0..100000]of longint;
    l:array[1..100000]of record ed,pre:longint; end;
    n,m,i,fa,a,b,tot,rt,len:longint;
    c:char;

procedure link(a,b:longint);
begin
    inc(tot);
    l[tot].pre:=lst[a];
    lst[a]:=tot;
    l[tot].ed:=b;
end;

procedure dfs(t:longint);
var k:longint;
begin
    inc(len);
    seq[len]:=1;
    id[len]:=t;
    k:=lst[t];
    while k<>0 do
    begin
        dfs(l[k].ed);
        k:=l[k].pre;
    end;
    inc(len);
    seq[len]:=-1;
    id[len]:=t;
end;

procedure pushdown(t:longint);
var l,r:longint;
begin
    l:=s[t].lc;
    r:=s[t].rc;
    if l<>0 then
    begin
        inc(s[l].plus,s[t].plus);
        inc(s[l].sum,int64(s[t].plus)*int64(s[l].cnt));
        inc(s[l].k,s[t].plus);
    end;
    if r<>0 then
    begin
        inc(s[r].plus,s[t].plus);
        inc(s[r].sum,int64(s[t].plus)*int64(s[r].cnt));
        inc(s[r].k,s[t].plus);
    end;
    s[t].plus:=0;
end;

procedure update(t:longint);
begin
    if t=0 then exit;
    if s[t].plus<>0 then pushdown(t);
    s[t].size:=s[s[t].lc].size+s[s[t].rc].size+1;
    s[t].cnt:=s[s[t].lc].cnt+s[s[t].rc].cnt+s[t].f;
    s[t].sum:=s[s[t].lc].sum+s[s[t].rc].sum+s[t].f*s[t].k;
end;

procedure build(var t:longint;l,r,fa:longint);
var mid:longint;
begin
    mid:=(l+r)>>1;
    inc(tot);
    t:=tot;
    s[t].fa:=fa;
    s[t].f:=seq[mid];
    s[t].k:=w[id[mid]];
    s[t].sum:=s[t].k;
    s[t].size:=1;
    s[t].cnt:=s[t].f;
    if seq[mid]=1 then pl[id[mid]]:=tot;
    if seq[mid]=-1 then pr[id[mid]]:=tot;
    if l<mid then build(s[t].lc,l,mid-1,t);
    if mid<r then build(s[t].rc,mid+1,r,t);
    update(t);
end;

procedure l_rotate(t:longint);
var p:longint;
begin
    p:=s[t].fa;
    s[p].rc:=s[t].lc;
    if s[t].lc<>0 then s[s[t].lc].fa:=p;
    s[t].fa:=s[p].fa;
    if p=s[s[p].fa].lc then s[s[p].fa].lc:=t;
    if p=s[s[p].fa].rc then s[s[p].fa].rc:=t;
    s[p].fa:=t;
    s[t].lc:=p;
    update(p);
    update(t);
end;

procedure r_rotate(t:longint);
var p:longint;
begin
    p:=s[t].fa;
    s[p].lc:=s[t].rc;
    if s[t].rc<>0 then s[s[t].rc].fa:=p;
    s[t].fa:=s[p].fa;
    if p=s[s[p].fa].lc then s[s[p].fa].lc:=t;
    if p=s[s[p].fa].rc then s[s[p].fa].rc:=t;
    s[p].fa:=t;
    s[t].rc:=p;
    update(p);
    update(t);
end;

procedure splay(t:longint);
begin
    while s[t].fa<>0 do
    begin
        if s[s[t].fa].plus<>0 then pushdown(s[t].fa);
        if s[s[s[t].fa].lc].plus<>0 then pushdown(s[s[t].fa].lc);
        if s[s[s[t].fa].rc].plus<>0 then pushdown(s[s[t].fa].rc);
        if t=s[s[t].fa].lc then r_rotate(t) else l_rotate(t);
    end;
    rt:=t;
end;

function query(t:longint):int64;
begin
    splay(t);
    exit(s[s[t].lc].sum+s[t].f*s[t].k);
end;

function rank(t:longint):longint;
begin
    splay(t);
    exit(s[s[t].lc].size+1);
end;

function getk(t,k:longint):longint;
begin
    if k=s[s[t].lc].size+1 then exit(t);
    if k<=s[s[t].lc].size then exit(getk(s[t].lc,k))
    else exit(getk(s[t].rc,k-s[s[t].lc].size-1));
end;

procedure move(x,y:longint);
var t,r1,r2:longint;
begin
    r1:=rank(pl[x])-1;
    r2:=rank(pr[x])+1;
    splay(getk(rt,r1));
    splay(getk(rt,r2));
    t:=s[s[rt].lc].rc;
    s[s[rt].lc].rc:=0;
    update(s[rt].lc);
    update(rt);
    splay(getk(rt,rank(pr[y])-1));
    splay(pr[y]);
    s[s[rt].lc].rc:=t;
    s[t].fa:=s[rt].lc;
    update(s[rt].lc);
    update(rt);
end;

procedure plus(t,d:longint);
var r1,r2:longint;
begin
    r1:=rank(pl[t])-1;
    r2:=rank(pr[t])+1;
    splay(getk(rt,r1));
    splay(getk(rt,r2));
    t:=s[s[rt].lc].rc;
    inc(s[t].sum,int64(d)*int64(s[t].cnt));
    inc(s[t].plus,d);
    inc(s[t].k,d);
    update(s[rt].lc);
    update(rt);
end;

begin
    readln(n);
    tot:=0;
    for i:=2 to n do
    begin
        read(fa);
        link(fa,i);
    end;
    for i:=1 to n do read(w[i]);
    len:=1;
    dfs(1);
    inc(len);
    tot:=0;
    build(rt,1,len,0);
    readln(m);
    for i:=1 to m do
    begin
        read(c,a);
        if c<>'Q' then read(b);
        readln;
        case c of
            'Q':writeln(query(pl[a]));
            'C':move(a,b);
            'F':plus(a,b);
        end;
    end;
end.