luogu2420 让我们异或吧

这题就没人用并查集吗，我弱弱地问一句

然而是先并，后查的

建立一个带权并查集

g[x]表示节点x到他直接父亲的异或值

根据异或的可乱搞的性质

注意并查集一定要先getf一下

然后合并同根据异或可乱搞的性质(rt所示)

mspaint真心毒瘤

查询的时候先getf一下

然后直接g[u]^g[v]即可

#include <bits/stdc++.h>

using namespace std;

int f[100010],g[100010],n,m;

int getf(int x)
{
    if(f[x]==x)
        return x;
    int fa=getf(f[x]);
    g[x]^=g[f[x]];
    return f[x]=fa;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        f[i]=i;
        g[i]=0;
    }
    for(int u,v,w,i=1;i<n;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        getf(u);
        getf(v);
        int fa=f[u];
        f[fa]=f[v];
        g[fa]=g[u]^g[v]^w;
    }
    scanf("%d",&m);
    for(int x,y,i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        getf(x);
        getf(y);
        printf("%d\n",g[x]^g[y]);
    }
    return 0;
}