A91492 正经题解

解题思路
直接求两节点异或和即可，因为两点公共祖先以上的多余权会异或两次抵消，数据范围大需要预处理优化
AC代码

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> edge[100005];
int xo[100005];

void dfs(int u, int fa){
    for(auto [v, w]:edge[u]){
        if(v==fa) continue;
        xo[v] = xo[u]^w;
        dfs(v, u);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int N, q;
    cin >> N;
    for(int i=1;i<N;++i){
        int u, v, w;
        cin >> u >> v >> w;
        edge[u].push_back({v, w});
        edge[v].push_back({u, w});
    }
    dfs(1, 0);
    cin >> q;
    while(q--){
        int x, y;
        cin >> x >> y;
        cout << (xo[x]^xo[y]) << endl;
    }
}

时间复杂度
$O(n+m)$，这题题干写挺好。