Sengxian's Blog

//  Created by Sengxian on 3/17/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  Spoj QTREE VII 链分治（巨坑之后的黎明）
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
using namespace std;

inline int ReadInt() {
    int n = 0, ch = getchar(); bool flag = false;
    while(!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while(isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return flag ? -n : n;
}

const int maxn = 100000 + 3, INF = 0x3f3f3f3f;
vector<int> G[maxn];
bool color[maxn]; // 0 - black 1 - white
int n, w[maxn], fa[maxn], id[maxn], idR[maxn], s[maxn], sz[maxn], bel[maxn], timestamp = 0;
int root[maxn];

int dfs1(int u, int f) {
    fa[u] = f, s[u] = 1;
    for (int i = 0; i < (int)G[u].size(); ++i) {
        int v = G[u][i];
        if (v != f) s[u] += dfs1(v, u);
    }
    return s[u];
}

void dfs2(int u, int num) {
    idR[timestamp] = u, id[u] = timestamp++, bel[u] = num;
    sz[num]++;
    int Max = 0, idx = -1;
    for (int i = 0; i < (int)G[u].size(); ++i) {
        int v = G[u][i];
        if (v != fa[u] && s[v] > Max) {Max = s[v], idx = v;}
    }
    if (Max == 0) return;
    dfs2(idx, num);
    for (int i = 0; i < (int)G[u].size(); ++i) {
        int v = G[u][i];
        if (v != fa[u] && v != idx) dfs2(v, v);
    }
}

const int maxNode = (1 << 17) * 2 + 10;
struct Node {
    int s, maxL, maxR, cleft, cright;
    Node(int s = 0, int maxL = -INF, int maxR = -INF, int cleft = 0, int cright = 0): s(s), maxL(maxL), maxR(maxR), cleft(cleft), cright(cright) {}
}seg[maxNode];
int ls[maxNode], rs[maxNode], segCnt = 0;

template <typename T>
struct Rint {
    bool operator()(const T &l , const T &r) const {return l > r;}
};
multiset<int, Rint<int> > ch[maxn], nch[maxn];

Node merge(const Node &lnode, const Node &rnode, bool flag) {
    Node newNode(lnode.s + rnode.s, lnode.maxL, rnode.maxR, lnode.cleft, rnode.cright);
    if (flag && lnode.cleft == lnode.s) newNode.maxL = max(newNode.maxL, rnode.maxL), newNode.cleft += rnode.cleft;
    if (flag && rnode.cleft == rnode.s) newNode.maxR = max(newNode.maxR, lnode.maxR), newNode.cright += lnode.cright;
    return newNode;
}

void maintain(int o, int u) {
    int d = max(w[u], ch[u].size() ? *ch[u].begin() : -INF);
    seg[o].maxL = seg[o].maxR = d;
    seg[o].s = seg[o].cleft = seg[o].cright = 1;
}

void buildTree(int o, int l, int r) {
    if (r - l == 1) {
        int u = idR[l];
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (v != fa[u] && bel[v] != bel[u]) {
                buildTree(root[v] = segCnt++, id[v], id[v] + sz[v]);
                if (color[u] == color[v]) ch[u].insert(seg[root[v]].maxL);
                else nch[u].insert(seg[root[v]].maxL);
            }
        }
        maintain(o, u);
    }else {
        int mid = (l + r) / 2;
        buildTree(ls[o] = segCnt++, l, mid);
        buildTree(rs[o] = segCnt++, mid, r);
        seg[o] = merge(seg[ls[o]], seg[rs[o]], color[idR[mid - 1]] == color[idR[mid]]);
    }
}

void process() {
    dfs1(0, -1);
    dfs2(0, 0);
    buildTree(root[0] = segCnt++, id[0], id[0] + sz[0]);
}

int query(int o, int l, int r, int tar) {
    int ans = -INF;
    if (r - l == 1) {
        ans = max(ans, seg[o].maxL);
        int head = bel[tar];
        if (head != 0 && seg[root[head]].cleft >= l + 1 - id[head]) {
            int fh = fa[head], fhh = bel[fh];
            if (color[fh] == color[tar]) ans = max(ans, query(root[fhh], id[fhh], id[fhh] + sz[fhh], fh));
        }
    }else {
        int mid = (l + r) / 2, idx = id[tar];
        if (idx < mid) {
            if (seg[ls[o]].cright >= mid - idx && color[tar] == color[idR[mid]]) ans = max(ans, seg[rs[o]].maxL);
            ans = max(ans, query(ls[o], l, mid, tar));
        }else {
            if (seg[rs[o]].cleft >= idx - mid + 1 && color[tar] == color[idR[mid - 1]]) ans = max(ans, seg[ls[o]].maxR);
            ans = max(ans, query(rs[o], mid, r, tar));
        }
    }
    return ans;
}

vector<int> path;
void findPath(int u) {
    while (u != -1) {
        path.push_back(u);
        u = fa[bel[u]];
    }
}

int X;
void modifyColor(int o, int l, int r, int i) {
    if (r - l == 1) {
        int u = idR[l];
        if (i + 1 != path.size()) {
            int nexT = bel[path[i + 1]];
            if ((color[u] == color[nexT] && nexT != X) || (color[u] != color[nexT] && nexT == X)) ch[u].erase(ch[u].find(seg[root[nexT]].maxL));
            else nch[u].erase(nch[u].find(seg[root[nexT]].maxL));
            modifyColor(root[nexT], id[nexT], id[nexT] + sz[nexT], i + 1);
            if (color[u] == color[nexT]) ch[u].insert(seg[root[nexT]].maxL);
            else nch[u].insert(seg[root[nexT]].maxL);
        }else swap(ch[u], nch[u]);
        maintain(o, u);
    }else {
        int mid = (l + r) / 2;
        if (id[path[i]] < mid) modifyColor(ls[o], l, mid, i);
        else modifyColor(rs[o], mid, r, i);
        seg[o] = merge(seg[ls[o]], seg[rs[o]], color[idR[mid - 1]] == color[idR[mid]]);
    }
}

void modifyWeight(int o, int l, int r, int i) {
    if (r - l == 1) {
        int u = idR[l];
        if (i + 1 != path.size()) {
            int nexT = bel[path[i + 1]];
            if (color[u] == color[nexT]) ch[u].erase(ch[u].find(seg[root[nexT]].maxL));
            else nch[u].erase(nch[u].find(seg[root[nexT]].maxL));
            modifyWeight(root[nexT], id[nexT], id[nexT] + sz[nexT], i + 1);
            if (color[u] == color[nexT]) ch[u].insert(seg[root[nexT]].maxL);
            else nch[u].insert(seg[root[nexT]].maxL);
        }
        maintain(o, u);
    }else {
        int mid = (l + r) / 2;
        if (id[path[i]] < mid) modifyWeight(ls[o], l, mid, i);
        else modifyWeight(rs[o], mid, r, i);
        seg[o] = merge(seg[ls[o]], seg[rs[o]], color[idR[mid - 1]] == color[idR[mid]]);
    }
}


int main() {
    n = ReadInt();
    for (int i = 0; i < n - 1; ++i) {
        int f = ReadInt() - 1, t = ReadInt() - 1;
        G[f].push_back(t), G[t].push_back(f);
    }
    for (int i = 0; i < n; ++i) color[i] = ReadInt();
    for (int i = 0; i < n; ++i) w[i] = ReadInt();
    process();
    int q = ReadInt();
    while (q--) {
        int op = ReadInt(), u = ReadInt() - 1;
        assert(op >= 0 && op < 3);
        if (op == 0) { //查询
            printf("%d\n", query(root[bel[u]], id[bel[u]], id[bel[u]] + sz[bel[u]], u));
        }else if(op == 1) { //修改颜色
            X = u, color[u] = !color[u];
            path.clear();
            findPath(u);
            reverse(path.begin(), path.end());
            modifyColor(root[0], id[0], id[0] + sz[0], 0);
        }else { //修改权值
            w[u] = ReadInt();
            path.clear();
            findPath(u);
            reverse(path.begin(), path.end());
            modifyWeight(root[0], id[0], id[0] + sz[0], 0);
        }
    }
    return 0;
}