前两天还在YY动态DFS序呢,这就冒了一个出来。


动态DFS序的郁闷之处在于不好维护dfs序上的end。而把反括号建出来正好能解决这个问题。


然后就splay写得飞慢不知道怎么回事。


用两个栈就可以迭代做出括号序列,自己YY出来的给自己赞一个。


然后是目前最长的代码和倒数第二慢的时间。

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>


using namespace std;


int _d_;

#define readInt(_x_) { \

int &_s_ = _x_; \

while (!isdigit(_d_ = getchar())); \

_s_ = 0; \

while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \

}

#define readOpt(_x_) { \

while (!isupper(_d_ = getchar())); \

_x_ = _d_; \

}


typedef long long qw;


#ifdef WIN32

#define lld "%I64d"

#else

#define lld "%lld"

#endif


struct edge {

int t;

edge *next;

};

struct splay_node {

int ls, rs, pt, sz, x;

qw v, a, s;

};


const int maxn = 200009;


int n, m, w[maxn];

int fa[maxn], dfb[maxn], dfe[maxn], dfo[maxn];

edge *ep, *head[maxn];


void dfsBuild() {

static int sa[maxn], sb[maxn];

int ta = 1, tb = 0, dfn = 0;

sa[ta] = 1;

memset(dfb, 0, sizeof(dfb));

while (ta) {

int p = sa[ta --];

while (tb && sb[tb] != fa[p])

dfe[sb[tb --]] = ++ dfn;

sb[++ tb] = p;

dfb[p] = ++ dfn;

for (edge* e = head[p]; e; e = e-> next)

sa[++ ta] = e-> t;

}

while (tb)

dfe[sb[tb --]] = ++ dfn;

for (int i = 1; i <= n; ++ i)

dfo[dfb[i]] = i, dfo[dfe[i]] = -i;

}


#define lRot(_q_) { \

int _p_ = t[_q_]. pt, _a_ = t[_p_]. pt; \

if (_a_) { \

if (_p_ == t[_a_]. ls) \

t[_a_]. ls = _q_; \

else \

t[_a_]. rs = _q_; \

} \

if (t[_q_]. rs) \

t[t[_q_]. rs]. pt = _p_; \

t[_p_]. ls = t[_q_]. rs; \

t[_q_]. rs = _p_; \

t[_q_]. pt = _a_; \

t[_p_]. pt = _q_; \

update(_p_); \

update(_q_); \

}

#define rRot(_q_) { \

int _p_ = t[_q_]. pt, _a_ = t[_p_]. pt; \

if (_a_) { \

if (_p_ == t[_a_]. ls) \

t[_a_]. ls = _q_; \

else \

t[_a_]. rs = _q_; \

} \

if (t[_q_]. ls) \

t[t[_q_]. ls]. pt = _p_; \

t[_p_]. rs = t[_q_]. ls; \

t[_q_]. ls = _p_; \

t[_q_]. pt = _a_; \

t[_p_]. pt = _q_; \

update(_p_); \

update(_q_); \

}

#define update(_p_) { \

t[_p_]. sz = t[t[_p_]. ls]. sz + t[t[_p_]. rs]. sz + t[_p_]. x; \

t[_p_]. s = t[t[_p_]. ls]. s + t[t[_p_]. rs]. s + t[_p_]. v + t[_p_]. a * t[_p_]. sz; \

}

#define pushDown(_p_) { \

if (t[_p_]. a) { \

if (t[_p_]. ls) { \

t[t[_p_]. ls]. a += t[_p_]. a; \

update(t[_p_]. ls); \

} \

if (t[_p_]. rs) { \

t[t[_p_]. rs]. a += t[_p_]. a; \

update(t[_p_]. rs); \

} \

if (t[_p_]. x > 0) \

t[_p_]. v += t[_p_]. a; \

else \

t[_p_]. v -= t[_p_]. a; \

t[_p_]. a = 0; \

} \

}


struct splay_tree {

splay_node t[maxn];

int cr, n;

splay_tree() {

t[0]. sz = 0;

t[0]. s = 0;

}

void dpath(int p) {

static int stc[maxn];

int tst = 1;

stc[1] = p;

for (; t[stc[tst]]. pt; ++ tst)

stc[tst + 1] = t[stc[tst]]. pt;

for (; tst; -- tst)

pushDown(stc[tst]);

}

void splay(int q) {

dpath(q);

while (t[q]. pt) {

int p = t[q]. pt, a = t[p]. pt;

if (!a || !t[a]. pt) {

if (q == t[p]. ls) {

lRot(q);

}

else {

rRot(q);

}

}

else {

if (p == t[a]. ls) {

if (q == t[p]. ls) {

lRot(p);

lRot(q);

}

else {

rRot(q);

lRot(q);

}

}

else {

if (q == t[p]. rs) {

rRot(p);

rRot(q);

}

else {

lRot(q);

rRot(q);

}

}

}

}

cr = q;

}

inline int build(int l, int r, int pt = 0) {

if (l >= r)

return 0;

int p = (l + r) >> 1;

t[p]. pt = pt;

t[p]. v = ((dfo[p] > 0) ? w[dfo[p]] : -w[-dfo[p]]);

t[p]. x = ((dfo[p] > 0) ? 1 : -1);

t[p]. a = 0;

t[p]. ls = build(l, p, p);

t[p]. rs = build(p + 1, r, p);

update(p);

if (!pt)

cr = p, n = r;

return p;

}

int tmax(int p) {

while (t[p]. rs)

p = t[p]. rs;

return p;

}

int tmin(int p) {

while (t[p]. ls)

p = t[p]. ls;

return p;

}

int getRange(int l, int r) {

if (l == 1 && r == n)

return cr;

else if (l == 1) {

splay(r);

int x = tmin(t[r]. rs);

splay(x);

return t[x]. ls;

}

else if (r == n) {

splay(l);

int x = tmax(t[l]. ls);

splay(x);

return t[x]. rs;

}

else {

splay(l);

int x = tmax(t[l]. ls);

splay(r);

int y = tmin(t[r]. rs);

splay(x);

splay(y);

return t[x]. rs;

}

}

inline qw getSum(int q) {

dpath(q);

return t[q]. s;

}

inline void add(int q, int v) {

t[q]. a += v;

update(q);

splay(q);

}

void cut(int q) {

int p = t[q]. pt;

dpath(q);

if (q == t[p]. ls)

t[p]. ls = 0;

else

t[p]. rs = 0;

t[q]. pt = 0;

update(p);

splay(p);

}

void link(int q, int p) {

splay(p);

if (t[p]. rs) {

int x = tmin(t[p]. rs);

splay(x);

}

dpath(p);

t[p]. rs = q;

t[q]. pt = p;

update(p);

splay(q);

}

};


splay_tree t;


int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif


readInt(n);

memset(head, 0, sizeof(head));

ep = new edge[n];

for (int i = 2; i <= n; ++ i) {

readInt(fa[i]);

ep-> t = i;

ep-> next = head[fa[i]];

head[fa[i]] = ep ++;

}

for (int i = 1; i <= n; ++ i)

readInt(w[i]);

dfsBuild();

t. build(1, n * 2);

readInt(m);

while (m --) {

char opt;

int x, y;

readOpt(opt);

if (opt == 'Q') {

readInt(x);

y = t. getRange(1, dfb[x]);

printf(lld "\n", t. getSum(y));

}

else if (opt == 'C') {

readInt(x);

readInt(y);

int a = t. getRange(dfb[x], dfe[x]);

t. cut(a);

t. link(a, dfb[y]);

}

else if (opt == 'F') {

readInt(x);

readInt(y);

int a = t. getRange(dfb[x], dfe[x]);

t. add(a, y);

}

}

}