Jabby's shadow

#include <cstdio>
#include <cctype>
#include <algorithm>

struct IO_Tp
{
    const static int _I_Buffer_Size = 4 << 20;
    char _I_Buffer[_I_Buffer_Size], *_I_pos = _I_Buffer;

    const static int _O_Buffer_Size = 4 << 20;
    char _O_Buffer[_O_Buffer_Size], *_O_pos = _O_Buffer;

    IO_Tp() { fread(_I_Buffer, 1, _I_Buffer_Size, stdin); }
    ~IO_Tp() { fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout); }

    IO_Tp &operator>>(int &res)
    {
        res = 0;
        while (!isdigit(*_I_pos))
            ++_I_pos;
        do
            res = res * 10 + (*_I_pos++ & 15);
        while (isdigit(*_I_pos));
        return *this;
    }

    char getop()
    {
        while (!isdigit(*_I_pos))
            ++_I_pos;
        return *_I_pos++ & 15;
    }

    IO_Tp &operator<<(int n)
    {
        static char _buf[10];
        char* _pos = _buf;
        do
            *_pos++ = '0' + n % 10;
        while (n /= 10);
        while (_pos != _buf)
            *_O_pos++ = *--_pos;
        return *this;
    }

    IO_Tp &operator<<(char ch)
    {
        *_O_pos++ = ch;
        return *this;
    }
} IO;

const bool compress = false, rake = true;

struct Splay_Tree
{
    static Splay_Tree *Null;

    void *operator new(size_t size);
    void *operator new[](size_t size);
    void operator delete(void *ptr);

    Splay_Tree *ch[3], *parent;
    bool rev;
    bool color, pc[2];
    int length, dist[2][2], res[2], pdist[2][2], pres[2];
    char lazy;

    Splay_Tree() : rev(false), color(0), length(0), lazy(-1)
    {
        static bool _init = false;
        if (!_init)
        {
            _init = true;
            Null = new Splay_Tree;
            Null->ch[0] = Null->ch[1] = Null->ch[2] = Null->parent = Null;
            Null->pc[0] = Null->pc[1] = true;
        }
        ch[0] = ch[1] = ch[2] = parent = Null;
        pc[0] = true, pc[1] = false;
        length = dist[0][0] = dist[0][1] = dist[1][0] = dist[1][1] = res[0] = res[1] = 0;
        pdist[0][0] = pdist[0][1] = pdist[1][0] = pdist[1][1] = pres[0] = pres[1] = 0;
    }

    bool is_root() const
    {
        return parent->ch[0] != this && parent->ch[1] != this;
    }

    template<const bool type>
    void pushup();

    template<const bool type>
    void pushdown();

    void reverse()
    {
        rev ^= 1, std::swap(ch[0], ch[1]);
        std::swap(dist[0][0], dist[1][0]), std::swap(dist[0][1], dist[1][1]);
        std::swap(res[0], res[1]);
        std::swap(pdist[0][0], pdist[1][0]), std::swap(pdist[0][1], pdist[1][1]);
    }

    bool dir() const
    {
        return parent->ch[1] == this;
    }

    Splay_Tree *sch(const int d, Splay_Tree *c)
    {
        return ch[d] = c, c->parent = this;
    }

    void modify(const bool _c)
    {
        if (pc[0] && pc[1])
            return;
        lazy = _c;
        this->color = _c;
        pc[_c] = true, pc[!_c] = false;
        dist[0][_c] = pdist[0][_c], dist[1][_c] = pdist[1][_c];
        dist[0][!_c] = dist[1][!_c] = 0;
        res[0] = res[1] = pres[_c];
    }

    template<const bool type>
    void rotate()
    {
        Splay_Tree *p = parent;
        p->pushdown<type>(), pushdown<type>();
        bool d = dir();
        if (parent = p->parent, p->parent != Splay_Tree::Null)
        {
            if (p->parent->ch[2] == p)
                p->parent->ch[2] = this;
            else
                p->parent->ch[p->dir()] = this;
        }
        p->sch(d, ch[!d])->pushup<type>(), sch(!d, p)->pushup<type>();
    }

    template<const bool type>
    Splay_Tree *splay(Splay_Tree *p = Null)
    {
        for (pushdown<type>(); parent != p && !is_root(); rotate<type>())
            if (parent->parent != p && !parent->is_root())
                parent->parent->pushdown<type>(), (parent->dir() == dir() ? parent : this)->rotate<type>();
        return this;
    }

    template<const bool type>
    Splay_Tree *splay_m(const bool d)
    {
        Splay_Tree *o = this;
        while (o->pushdown<type>(), o->ch[d] != Splay_Tree::Null)
            o = o->ch[d];
        return o->splay<type>(parent);
    }
};
Splay_Tree *Splay_Tree::Null;

const int Max_N = 100005;

const int _M_size = Max_N * 3;
char _M[_M_size * sizeof(Splay_Tree)], *_M_cur = _M + sizeof(_M);
void *_M_rc[_M_size], **_M_rc_cur = _M_rc;

inline void *Splay_Tree::operator new(size_t size) { return _M_rc_cur != _M_rc ? *--_M_rc_cur : _M_cur -= size; }
inline void *Splay_Tree::operator new[](size_t size) { return _M_cur -= size; }
inline void Splay_Tree::operator delete(void *ptr) { *_M_rc_cur++ = ptr; }

template<>
inline void Splay_Tree::pushup<compress>()
{
    pc[color] = ch[0]->pc[color] && ch[1]->pc[color], pc[!color] = false;
    length = ch[0]->length + ch[1]->length;
    dist[0][0] = ch[0]->dist[0][0], dist[0][1] = ch[0]->dist[0][1];
    dist[1][0] = ch[1]->dist[1][0], dist[1][1] = ch[1]->dist[1][1];
    res[0] = ch[0]->res[0], res[1] = ch[1]->res[1];
    if (ch[0]->pc[color])
    {
        dist[0][color] = std::max(dist[0][color], ch[0]->length + std::max(ch[1]->dist[0][color], ch[2]->dist[0][color]));
        res[0] = std::max(std::max(res[0], std::max(ch[1]->dist[0][color] ? ch[1]->res[0] : 0, ch[2]->res[color])), std::max(ch[0]->dist[1][color] + ch[1]->dist[0][color], std::max(ch[0]->dist[1][color], ch[1]->dist[0][color]) + ch[2]->dist[0][color]));
    }
    if (ch[1]->pc[color])
    {
        dist[1][color] = std::max(dist[1][color], ch[1]->length + std::max(ch[0]->dist[1][color], ch[2]->dist[0][color]));
        res[1] = std::max(std::max(res[1], std::max(ch[0]->dist[1][color] ? ch[0]->res[1] : 0, ch[2]->res[color])), std::max(ch[0]->dist[1][color] + ch[1]->dist[0][color], std::max(ch[0]->dist[1][color], ch[1]->dist[0][color]) + ch[2]->dist[0][color]));
    }
    pdist[0][0] = std::max(ch[0]->pdist[0][0], ch[0]->length + std::max(ch[1]->pdist[0][0], ch[2]->dist[0][0]));
    pdist[0][1] = std::max(ch[0]->pdist[0][1], ch[0]->length + std::max(ch[1]->pdist[0][1], ch[2]->dist[0][1]));
    pdist[1][0] = std::max(ch[1]->pdist[1][0], ch[1]->length + std::max(ch[0]->pdist[1][0], ch[2]->dist[0][0]));
    pdist[1][1] = std::max(ch[1]->pdist[1][1], ch[1]->length + std::max(ch[0]->pdist[1][1], ch[2]->dist[0][1]));
    pres[0] = std::max(std::max(std::max(ch[0]->pres[0], ch[1]->pres[0]), ch[2]->res[0]), std::max(ch[0]->pdist[1][0] + ch[1]->pdist[0][0], std::max(ch[0]->pdist[1][0], ch[1]->pdist[0][0]) + ch[2]->dist[0][0]));
    pres[1] = std::max(std::max(std::max(ch[0]->pres[1], ch[1]->pres[1]), ch[2]->res[1]), std::max(ch[0]->pdist[1][1] + ch[1]->pdist[0][1], std::max(ch[0]->pdist[1][1], ch[1]->pdist[0][1]) + ch[2]->dist[0][1]));
}

template<>
inline void Splay_Tree::pushup<rake>()
{
    dist[0][0] = std::max(std::max(ch[0]->dist[0][0], ch[1]->dist[0][0]), ch[2]->dist[0][0]);
    dist[0][1] = std::max(std::max(ch[0]->dist[0][1], ch[1]->dist[0][1]), ch[2]->dist[0][1]);
    res[0] = std::max(std::max(ch[0]->dist[0][0] + ch[1]->dist[0][0], ch[2]->dist[0][0] + std::max(ch[0]->dist[0][0], ch[1]->dist[0][0])), std::max(ch[2]->dist[0][0] ? ch[2]->res[0] : 0, std::max(ch[0]->res[0], ch[1]->res[0])));
    res[1] = std::max(std::max(ch[0]->dist[0][1] + ch[1]->dist[0][1], ch[2]->dist[0][1] + std::max(ch[0]->dist[0][1], ch[1]->dist[0][1])), std::max(ch[2]->dist[0][1] ? ch[2]->res[0] : 0, std::max(ch[0]->res[1], ch[1]->res[1])));
}

template<>
inline void Splay_Tree::pushdown<compress>()
{
    if (rev)
        ch[0]->reverse(), ch[1]->reverse(), rev = false;
    if (lazy != -1)
        ch[0]->modify(lazy), ch[1]->modify(lazy), lazy = -1;
}

template<>
inline void Splay_Tree::pushdown<rake>() { }

void splay_splice(Splay_Tree *o)
{
    o->splay<rake>();
    o = o->parent->splay<compress>();
    Splay_Tree *c = o->ch[2];
    c->pushdown<rake>();
    if (o->ch[1] != Splay_Tree::Null)
        std::swap(o->ch[1]->parent, c->ch[2]->parent), std::swap(o->ch[1], c->ch[2]);
    else
    {
        o->sch(1, c->ch[2]);
        if (c->ch[0] != Splay_Tree::Null)
            c->ch[0]->splay_m<rake>(1), c->ch[0]->sch(1, c->ch[1]), o->ch[2] = c->ch[0];
        else
            c->ch[1]->pushdown<rake>(), o->ch[2] = c->ch[1];
        delete c, c = o->ch[2], c->parent = o;
    }
    c->pushup<rake>(), o->pushup<compress>(), o->ch[1]->rotate<compress>();
}

void access(Splay_Tree *o)
{
    o->splay<compress>();
    if (o->ch[1] != Splay_Tree::Null)
    {
        Splay_Tree *c = new Splay_Tree;
        c->sch(0, o->ch[2]), c->sch(2, o->ch[1]), c->pushup<rake>();
        o->ch[1] = Splay_Tree::Null, o->sch(2, c), o->pushup<compress>();
    }
    while (o->parent != Splay_Tree::Null)
        splay_splice(o->parent);
}

inline void evert(Splay_Tree *o)
{
    access(o), o->reverse(), o->pushdown<compress>();
}

inline void link(Splay_Tree *o1, Splay_Tree *o2, const int c)
{
    access(o1), evert(o2), o2->pushdown<compress>();
    Splay_Tree *e = new Splay_Tree;
    e->pc[1] = true, e->length = c;
    o2->sch(0, e)->pushup<compress>(), o1->sch(1, o2)->pushup<compress>();
}

int N, M;
int p[Max_N];
Splay_Tree *node0;
#define node(x) (node0 + x)

int main(int argc, char **argv)
{
    IO >> N;
    node0 = new Splay_Tree[N + 1];

    for (int i = 2; i <= N; ++i)
        IO >> p[i];
    for (int i = 2, c; i <= N; ++i)
        IO >> c, link(node(i), node(p[i]), c);

    IO >> M;
    while (M--)
        switch (IO.getop())
        {
            int v, w, c;

            case 1:
                IO >> v;
                access(node(v)), node(v)->res[1] ? IO << node(v)->res[1] << '\n' : IO << 'Q' << 'w' << 'Q' << '\n';
                break;

            case 2:
                IO >> v >> w >> c;
                evert(node(v)), access(node(w)), node(w)->modify(c - 1);
                break;
        }

    return 0;
}