Beauty of Trees（带权并查集）

题目

https://www.nowcoder.com/acm/contest/119/A

题目大意

每次查询告诉你[l,r]之间的数的异或和，如果遇到不正确的查询，输出查询编号。

算法思路

• 因为异或和前缀是不影响他的值，所以我们只需要将l和r连线，以异或值为权值，带权并查集即可。
• 每次查询如果l和r在同一集合中，检查与其值是否相符即可。若不在，直接相连即可。
• 带权并查集的操作

int Find(int x)
{
    if(x==fa[x])return x;
    int temp=fa[x];
    fa[x]=Find(fa[x]);//路径压缩
    rnk[x]=rnk[x]^rnk[temp];//更新rnk值
    return fa[x];
}

合并操作

 int ru=Find(u);
        int rv=Find(v);
        if(ru!=rv) {
            fa[ru]=rv;
            rnk[ru]=k^rnk[u]^rnk[v];
/*这里需要想一想；然后只更新了根节点的值，
子节点的值可以在后续查询find的时候更新*/
        }

• 为了方便操作，采用左开右闭（常规操作）

代码

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=1e5+5;
int fa[N];
ll rnk[N];
void Init(int n)
{
    for(int i=0;i<=n;i++)
    {
        fa[i]=i;
        rnk[i]=0;
    }
}
int Find(int x)
{
    if(x==fa[x])return x;
    int temp=fa[x];
    fa[x]=Find(fa[x]);
    rnk[x]=rnk[x]^rnk[temp];
    return fa[x];
}

int main()
{
    int n,m;
    while(cin>>n>>m){
        Init(n+1);
        int flag=0;
    for(int i=1;i<=m;i++){
         int u,v;
         ll k;
        scanf("%d%d%lld",&u,&v,&k);
        v++;
        int ru=Find(u);
        int rv=Find(v);
        if(ru!=rv) {
            fa[ru]=rv;
            rnk[ru]=k^rnk[u]^rnk[v];
        }
        else
        {
            if((rnk[v]^rnk[u])!=k) {flag=1;cout<<i<<endl;}
        }
    }
    if(!flag) cout<<-1<<endl;
    }
    return 0;
}