目录
#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 100005;
int n, m, rt, cur;
ll a[N], t[N * 4], lz[N * 4];
int sz[N], f[N][20], dep[N], sn[N], tp[N], dfn[N], rk[N];
vector<int> g[N];

void d1(int u, int p, int d) {
    sz[u] = 1;
    f[u][0] = p;
    dep[u] = d;
    for (int i = 1; i < 20; i++) f[u][i] = f[f[u][i - 1]][i - 1];
    for (int v : g[u]) {
        if (v == p) continue;
        d1(v, u, d + 1);
        sz[u] += sz[v];
        if (sz[v] > sz[sn[u]]) sn[u] = v;
    }
}

void d2(int u, int t) {
    tp[u] = t;
    dfn[u] = ++cur;
    rk[cur] = u;
    if (sn[u]) d2(sn[u], t);
    for (int v : g[u]) {
        if (v == f[u][0] || v == sn[u]) continue;
        d2(v, v);
    }
}

void bld(int p, int l, int r) {
    if (l == r) {
        t[p] = a[rk[l]];
        return;
    }
    int mid = (l + r) >> 1;
    bld(p << 1, l, mid);
    bld(p << 1 | 1, mid + 1, r);
    t[p] = t[p << 1] + t[p << 1 | 1];
}

void psd(int p, int l, int r) {
    if (lz[p]) {
        int mid = (l + r) >> 1;
        lz[p << 1] += lz[p];
        lz[p << 1 | 1] += lz[p];
        t[p << 1] += lz[p] * (mid - l + 1);
        t[p << 1 | 1] += lz[p] * (r - mid);
        lz[p] = 0;
    }
}

void upd(int p, int l, int r, int ql, int qr, ll v) {
    if (ql > qr) return;
    if (ql <= l && r <= qr) {
        t[p] += v * (r - l + 1);
        lz[p] += v;
        return;
    }
    psd(p, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid) upd(p << 1, l, mid, ql, qr, v);
    if (qr > mid) upd(p << 1 | 1, mid + 1, r, ql, qr, v);
    t[p] = t[p << 1] + t[p << 1 | 1];
}

ll ask(int p, int l, int r, int ql, int qr) {
    if (ql > qr) return 0;
    if (ql <= l && r <= qr) return t[p];
    psd(p, l, r);
    int mid = (l + r) >> 1;
    ll res = 0;
    if (ql <= mid) res += ask(p << 1, l, mid, ql, qr);
    if (qr > mid) res += ask(p << 1 | 1, mid + 1, r, ql, qr);
    return res;
}

int lca(int u, int v) {
    while (tp[u] != tp[v]) {
        if (dep[tp[u]] < dep[tp[v]]) swap(u, v);
        u = f[tp[u]][0];
    }
    return dep[u] < dep[v] ? u : v;
}

int get(int u, int v) {
    for (int i = 19; i >= 0; i--) {
        if (dep[f[v][i]] > dep[u]) v = f[v][i];
    }
    return v;
}

void mP(int u, int v, ll k) {
    while (tp[u] != tp[v]) {
        if (dep[tp[u]] < dep[tp[v]]) swap(u, v);
        upd(1, 1, n, dfn[tp[u]], dfn[u], k);
        u = f[tp[u]][0];
    }
    if (dep[u] > dep[v]) swap(u, v);
    upd(1, 1, n, dfn[u], dfn[v], k);
}

ll qP(int u, int v) {
    ll res = 0;
    while (tp[u] != tp[v]) {
        if (dep[tp[u]] < dep[tp[v]]) swap(u, v);
        res += ask(1, 1, n, dfn[tp[u]], dfn[u]);
        u = f[tp[u]][0];
    }
    if (dep[u] > dep[v]) swap(u, v);
    res += ask(1, 1, n, dfn[u], dfn[v]);
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 2; i <= n; i++) {
        int p; cin >> p;
        g[p].push_back(i);
        g[i].push_back(p);
    }

    d1(1, 0, 1);
    d2(1, 1);
    bld(1, 1, n);
    rt = 1;

    cin >> m;
    while (m--) {
        int op, u, v;
        ll k;
        cin >> op;
        if (op == 1) {
            cin >> rt;
        } else if (op == 2) {
            cin >> u >> v >> k;
            mP(u, v, k);
        } else if (op == 3) {
            cin >> u >> k;
            if (u == rt) {
                upd(1, 1, n, 1, n, k);
            } else {
                int lc = lca(u, rt);
                if (lc != u) {
                    upd(1, 1, n, dfn[u], dfn[u] + sz[u] - 1, k);
                } else {
                    int s = get(u, rt);
                    upd(1, 1, n, 1, dfn[s] - 1, k);
                    upd(1, 1, n, dfn[s] + sz[s], n, k);
                }
            }
        } else if (op == 4) {
            cin >> u >> v;
            cout << qP(u, v) << "\n";
        } else {
            cin >> u;
            if (u == rt) {
                cout << ask(1, 1, n, 1, n) << "\n";
            } else {
                int lc = lca(u, rt);
                if (lc != u) {
                    cout << ask(1, 1, n, dfn[u], dfn[u] + sz[u] - 1) << "\n";
                } else {
                    int s = get(u, rt);
                    cout << ask(1, 1, n, 1, dfn[s] - 1) + ask(1, 1, n, dfn[s] + sz[s], n) << "\n";
                }
            }
        }
    }

    return 0;
}

0 条评论

目前还没有评论...