“华为杯”杭州电子科技大学2023新生编程大赛 1005

树 - HDU 7406

$xordist(i,j)=xordist(i,k) \oplus xordist(k,j)$

在数轴和树上都是成立的

那么原式变成 $\sum_{i=l}^{r}xordist(i,k) \oplus xordist(k,j)$

这里 k 指定为 1 号点

就变成了一个很简单的拆位考虑贡献的问题了

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
typedef long long ll;

const int N = 1e5 + 100;
vector<pair<int, int>> g[N];
int dist[N], pre[N][50];

void init(int n) {
    for(int i = 0; i <= n; i++) g[i].clear();
}

void dfs(int x, int fa) {
    for(auto [y, v] : g[x]) {
        if(y == fa) continue;
        dist[y] = dist[x] ^ v;
        dfs(y, x);
        // cout << y << ' ' << dist[y] << endl;
    }
}

void solve() {
    int n; cin >> n;
    init(n);
    for(int i = 1; i < n; i++) {
        int x, y, v; cin >> x >> y >> v;
        g[x].push_back({y, v});
        g[y].push_back({x, v});
    }

    dfs(1, 1);

    // pre 1的个数
    for(int i = 1; i <= n; i++) {
        int val = dist[i] ^ dist[1];
        for(int j = 0; j <= 30; j++) {
            pre[i][j] = pre[i - 1][j] + (val >> j & 1);
        }
    }

    int q; cin >> q;
    while(q--) {
        int l, r, x; cin >> l >> r >> x;
        int val = dist[1] ^ dist[x];
        ll ans = 0;
        for(int i = 0; i <= 30; i++) {
            int num1 = pre[r][i] - pre[l - 1][i];
            int num0 = r - l + 1 - num1;
            if(val >> i & 1) ans += (1 << i) * num0;
            else ans += (1 << i) * num1;
        }
        cout << ans << endl;
    }

}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    
    int T = 1; cin >> T;
    while(T--) solve();
    // solve();
    
    return 0;
}