为什么不用神奇伟大的 STL？

记录这个树的 Euler 遍历：$I_v = [l_v, r_v]$ 表示 $v$ 节点的区间，$D_v$ 表示 $v$ 节点的深度。对于每一个深度 $D_v = d$，保存一个集合

我们来考虑一下操作的转化。

• 迁移操作：对于每个点 $u$，找到祖先 $a$（当且仅当 $I_u \subset I_a$），并将 $k_u$ 迁移到 $k_a$ 上。这实际上是两个集合的合并。
• 迁入操作：将 $S_d$ 的对应位置修改。
• 调查操作：查询 $S_{D_v}$ 的对应位置的 $k$-值。

我们采用一个懒计算的方式：对于迁移，采用启发式合并，得到一个多重集。对于调查，由于我们维护 multiset，所以可以逐一遍历，得到 $S_{D_v}$ 的对应真实 $k_v$ 值后将这些 $(l_v, k'_v)$ 全部删去，只保留真实的 $(l_v, k_v)$。

如果将 $(l, k)$ 对视为一个点，初始有 $n$ 个点，每一个调查加入一个点，因此最多 $n + q$ 个点；每个点只会被遍历一次，而启发式合并的复杂度是容易证明的，因此复杂度正确（两个 $\log$）。

template <class Tp>
void merge(multiset<Tp> &S, multiset<Tp> &T) {
    if (S.size() < T.size()) swap(S, T);
    for (auto x : T) S.insert(x);
    T.clear();
}

int main() {
    int n;
    cin >> n;
    vector<int> p(n), dep(n, -1);
    vector<vector<int>> tr(n);
    for (int i : range(1, n)) cin >> p[i], p[i]--, tr[p[i]] += i;
    vector<i64> a(n);
    for (i64 &x : a) cin >> x;

    vector<int> l(n), r(n);
    int cur = 0;
    auto dfs = [&](auto &&slf, int x) -> void {
        l[x] = cur++, dep[x] = dep[p[x]] + 1;
        for (int y : tr[x]) slf(slf, y);
        r[x] = cur++;
    };
    dfs(dfs, 0);

    vector<multiset<array<i64, 2>>> S(n);
    for (int i : range(n)) S[dep[i]].insert({l[i], a[i]});

    int q;
    cin >> q;
    for (int _ : range(q)) {
        i64 op, x, y, cnt;
        cin >> op;
        if (op == 1)
            cin >> x >> y, merge(S[y], S[x]);
        else if (op == 2)
            cin >> x >> cnt, x--, S[dep[x]].insert({l[x], cnt});
        else {
            cin >> x, x--;
            i64 d = dep[x], ans = 0;
            auto lm = S[d].lower_bound({l[x], 0}), rm = S[d].upper_bound({r[x], 0});
            for (auto it = lm; it != rm; it = S[d].erase(it)) ans += (*it)[1];
            S[d].insert({l[x], ans});
            cout << ans << endl;
        }
    }
}

来一篇说人话的题解。

bfs 序转区间是没有前途的，因为线段树合并不能直接合并两段不等长的区间，所以不太能每个点都直接维护。

考虑一些智慧的东西。每次合并的时候不直接对位合并，而是直接把 $deep=x$ 的集合整个合并到 $deep=y$ 的集合上，这里直接把对位扔掉。

考虑查询的过程，实际上就是考虑那些子树内的修改，由于所有的修改都被你全提到当前 $deep$ 所对应的集合上了，所以问题转换成集合内子树贡献求和，直接下标 dfn 序，区间求和即可。

综上，每个深度维护一棵以 dfn 序为下标的线段树，合并操作直接线段树合并，修改操作单点改，单点查询直接求该点深度对应的那棵线段树的子树 dfn 区间和。