没 $f$ 直接回滚莫队就行了。

有 $f$ 我们只需要保证一个块内的询问数不超过根号，然后一开始不把这个块内 $f$ 的边加进并查集，等到查询时加进去就行了。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 2e5 + 5;
constexpr int B = 400;

int n, q, a[N];
int u[N], v[N];

struct UnionFind {
    int f[N], sz[N], val[N], ans;
    pair<int, int> st[N]; int tot;
    int find(int x) { return f[x] == x ? x : find(f[x]); }
    void init() {
        ans = tot = 0;
        for (int i = 1; i <= n; ++i) f[i] = i, sz[i] = 1, val[i] = a[i], ans = max(ans, a[i]);
    }
    void merge(int i) {
        int u = ::u[i], v = ::v[i];
        u = find(u); v = find(v);
        if (u == v) return;
        if (sz[u] > sz[v]) swap(u, v);
        st[++tot] = make_pair(u,  ans);
        f[u] = v, sz[v] += sz[u], val[v] += val[u];
        ans = max(ans, val[v]);
    }
    void back(int lst) {
        while (tot > lst) {
            const auto [u, a] = st[tot--];
            int v = f[u];
            f[u] = u, sz[v] -= sz[u], val[v] -= val[u];
            ans = a;
        }
    }
} F;

struct Question {
    int l, r, f, id;
    bool operator< (const Question a) const {
        return l < a.l;
    }
} Q[N];
int L[N], R[N], tot; // 第 [L[i], R[i]] 个问题需要被放在一块内解决
int Ans[N];
bool die[N];

void solve() {
    cin >> n;
    for (int i = 1; i < n; ++i) cin >> u[i] >> v[i];
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cin >> q;
    for (int i = 1; i <= q; ++i) {
        cin >> Q[i].l >> Q[i].r >> Q[i].f; Q[i].id = i;
    }
    sort(Q + 1, Q + q + 1);
    tot = 1; L[tot] = R[tot] = 1;
    while (1) {
        while (R[tot] < q && R[tot] - L[tot] < B && Q[R[tot] + 1].l - Q[L[tot]].l < B) {
            ++R[tot];
        }
        if (R[tot] == q) break;
        ++tot; L[tot] = R[tot] = R[tot - 1] + 1;
    }

    for (int i = 1; i <= tot; ++i) {
        const int be = Q[R[i]].l;
        int x = be + 1, y = be;
        sort(Q + L[i], Q + R[i] + 1, [&](Question &a, Question &b) { return a.r < b.r; });
        F.init();
        memset(die, 0, sizeof die);
        for (int k = L[i]; k <= R[i]; ++k) die[Q[k].f] = true;
        // for (int k = 1; k < n; ++k) cerr << die[k] << " \n"[k == n - 1];
        for (int k = L[i]; k <= R[i]; ++k) {
            const auto [l, r, f, id] = Q[k];
            if (r <= be) {
                int lst = F.tot;
                for (int p = l; p <= r; ++p) if (p != f) F.merge(p);
                Ans[id] = F.ans;
                F.back(lst);
                continue;
            }
            // cerr << id << ' ' << x << ' ' << y << '\n';
            while (y < r) { ++y; if (!die[y]) F.merge(y); }
            // assert(y == r);
            int lst = F.tot;
            while (x > l) { --x; if (!die[x]) F.merge(x); }
            // assert(x == l);
            for (int p = L[i]; p <= R[i]; ++p)
                if (Q[p].f >= x && Q[p].f <= y && Q[p].f != f) F.merge(Q[p].f);
            Ans[id] = F.ans;
            F.back(lst);
            x = be + 1;
        }
    }

    for (int i = 1; i <= q; ++i) cout << Ans[i] << '\n';
}

int main(void) {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}