A Possible Tree (带权并查集）

Possible Tree

题意

给你一棵树，q个询问，问的是x->y路径上的异或和为val , 问你最多有几个询问是真的？

带权并查集。由于异或的特点，假设某个点为根，比如0，那么比如2->5的异或值，就是2->1的异或值和5->1的异或值异或一下。所以我们用yihuo[i]来表示i到源点的异或和。如果两个数的源点已经一样，那么判断一下val==yihuo[i]^yihuo[j]即可，若是不一样，就把他们union，同时yihuo[rootp]=yihuo[p]^yihuo[q]^val。

看！代码

#include <bits/stdc++.h>
using namespace std;
int fa[100010],yihuo[100010];
int Find(int x)
{
    if(x!=fa[x])
    {
        int tmp=fa[x];
        fa[x]=Find(fa[x]);
        yihuo[x]^=yihuo[tmp];
        return fa[x];
    }
    return x;
}

bool Union(int p,int q,int val)
{
    int rp=Find(p),rq=Find(q);
    if(rp!=rq)
    {
        fa[rp]=rq;
        yihuo[rp]=yihuo[p]^yihuo[q]^val;
        return true;
    }
    if((yihuo[p]^yihuo[q])!=val)
        return false;
    return true;
}
void init(int n)
{
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;yihuo[i]=0;
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,k,u,v,val;
        scanf("%d%d",&n,&k);
        init(n);
        for(int i=0;i<n-1;i++)
            scanf("%d%d",&u,&v);
        int flag=1,ans=0;
        for(int i=0;i<k;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            if(!Union(u,v,val)&&flag)
            {
                flag=0;
                ans=i;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}