思路与算法

建立点分治重心层级。每个重心存其分治块所有点的原编号及到重心距离，并为每个相邻分支另存一张同类表，排序后做距离前缀和。每点记录各祖先重心、距离和所处分支。查询编号区间时，对每层加全表的距离和加数量乘dist(x,c)，再减掉同分支表的同一项。

正确性说明

不同分支点到x的树路径经过当前重心，距离分解为两段和。与x同分支的点暂不适用该分解，整项扣除并交给下一层。每个目标点会在首次分离的重心或自身重心恰好被计一次，故总和准确，且与查询顺序无关，可真实在线解码。

复杂度

找各层重心和遍历O(nlogn)，逐层编号排序及前缀初始化O(nlog²n)，每查询O(log²n)，总O(nlog²n+mlog²n)，空间O(nlogn)。分治递归深度O(logn)，块内深树遍历使用显式栈。

易错点

原编号区间与DFS序无关，表必须按原编号排序。距离、前缀和及数量乘距离用64位。type=1时三个参数均异或上次答案模n，先解码再转0基下标。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct List {
    vector<pair<int, ll>> a;
    vector<ll> s;
    void build() {
        sort(a.begin(), a.end());
        s.assign(a.size() + 1, 0);
        for (int i = 0; i < (int)a.size(); i++)
            s[i + 1] = s[i] + a[i].second;
    }
    pair<ll, ll> query(int l, int r) {
        int x = lower_bound(a.begin(), a.end(), make_pair(l, LLONG_MIN)) - a.begin(),
            y = upper_bound(a.begin(), a.end(), make_pair(r, LLONG_MAX)) - a.begin();
        return {y - x, s[y] - s[x]};
    }
};
struct P {
    int c, b;
    ll d;
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, type;
    cin >> n >> m >> type;
    vector<vector<pair<int, ll>>> g(n);
    for (int i = 1, u, v; i < n; i++) {
        ll w;
        cin >> u >> v >> w;
        --u;
        --v;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    vector<int> dead(n), par(n), sz(n);
    vector<List> all(n), sub;
    vector<vector<P>> info(n);
    function<void(int)> build = [&](int rt) {
        vector<int> ord(1, rt);
        par[rt] = -1;
        for (int i = 0; i < (int)ord.size(); i++) {
            int u = ord[i];
            for (auto edge : g[u])
                if (!dead[edge.first] && edge.first != par[u]) {
                    par[edge.first] = u;
                    ord.push_back(edge.first);
                }
        }
        int c = rt, N = ord.size(), best = N;
        for (int i = N - 1; i >= 0; i--) {
            int u = ord[i], mx = 0;
            sz[u] = 1;
            for (auto edge : g[u])
                if (!dead[edge.first] && par[edge.first] == u) {
                    sz[u] += sz[edge.first];
                    mx = max(mx, sz[edge.first]);
                }
            mx = max(mx, N - sz[u]);
            if (mx < best) {
                best = mx;
                c = u;
            }
        }
        dead[c] = 1;
        all[c].a.push_back({c, 0});
        info[c].push_back({c, -1, 0});
        for (auto edge : g[c])
            if (!dead[edge.first]) {
                int v = edge.first;
                ll w = edge.second;
                int b = sub.size();
                sub.emplace_back();
                vector<tuple<int, int, ll>> st{{v, c, w}};
                for (int i = 0; i < (int)st.size(); i++) {
                    int u = get<0>(st[i]), p = get<1>(st[i]);
                    ll d = get<2>(st[i]);
                    all[c].a.push_back({u, d});
                    sub[b].a.push_back({u, d});
                    info[u].push_back({c, b, d});
                    for (auto e : g[u])
                        if (!dead[e.first] && e.first != p)
                            st.push_back({e.first, u, d + e.second});
                }
                sub[b].build();
            }
        all[c].build();
        for (auto e : g[c])
            if (!dead[e.first])
                build(e.first);
    };
    build(0);
    ll last = 0;
    while (m--) {
        int l, r, x;
        cin >> l >> r >> x;
        if (type) {
            l ^= last;
            r ^= last;
            x ^= last;
        }
        --l;
        --r;
        --x;
        ll ans = 0;
        for (auto p : info[x]) {
            auto a = all[p.c].query(l, r);
            ans += a.second + a.first * p.d;
            if (p.b >= 0) {
                auto b = sub[p.b].query(l, r);
                ans -= b.second + b.first * p.d;
            }
        }
        cout << ans << '\n';
        last = ans % n;
    }
}