学步园

题目链接：Click here~~

题意：

有n个数X0~Xn-1，开始时你不知道它们的值，逐步给你信息：1、直接给出 Xp 的值v。2、给出Xp ^ Xq的值v。然后在线询问某些(15个) Xi 异或的值。

解题思路：

好神奇的并查集啊，据说是偏移向量，基本完全仿照别人的，主要说下思路。

对于这种询问，我们并不一定要知道每个 Xi 的值，就可知道结果。

由于 Xp ^ 0 = Xp，我们可以虚拟一个数 Xn = 0，对于第1种信息，就等价于给出 Xp ^ Xn = v，与第2种信息格式一致。

从而，所有的信息都是两两相关的。那么，能不能和并查集联系起来呢？

我们YY一下，把互相有关的信息全部放入一个集合。

那么，对于集合间 节点 间的异或运算，由于没有信息，我们无从下手。

所以，我们只能先将每一个集合内的异或运算计算完毕后，再将所得到的值做异或运算得到最终的解。

而对于集合内 节点 间的异或运算可以看做 节点与根节点异或的值 间做异或运算。

并且当且仅当有奇数个数字参与运算的时候，才与根节点的值有关。并且，只有 Xn 所在的集合才知道根节点的值（想一想，为什么）。

所以为了方便，对于 Xn 的集合内我们以 Xn 为根，如果与它的值有关，也是 ^0，对结果无影响。

这样，我们只要维护好这个 节点与根节点异或的值 就可以不用知道每个节点的值从而将问题更好的解决。

而对于维护操作，就留给读者参照代码自己慢慢理解了。其中有很多细节，好几处代码的顺序不能颠倒，望有心人自己发现。

#include <map>
#include <stdio.h>
#include <string.h>

using namespace std;

#define N 20012

int n,pre[N],val[N];

int Root(int x)
{
    if(pre[x] == -1)
        return x;
    int rt = Root(pre[x]);                      //fantasy~
    val[x] ^= val[pre[x]];                      //as above
    return pre[x] = rt;
}

bool Union(int a,int b,int v)
{
    int r1 = Root(a);
    int r2 = Root(b);
    if(r1 == r2)
        return (val[a]^val[b]) == v;            //the priority of '^' is lower than '=='.
    if(r2 == n)
        swap(r1,r2);
    val[r2] = val[a]^val[b]^v;                  //think about why
    pre[r2] = r1;
    return true;
}

int main()
{
    int Q,p,q,v,k,ncase=0;
    char cmd,ccmd[30];
    map<int,int> M;
    while(scanf("%d%d%*c",&n,&Q),n)
    {
        printf("Case %d:\n",++ncase);
        memset(pre,-1,sizeof(pre));
        memset(val,0,sizeof(val));
        bool No = false;
        int facts = 0;
        while(Q--)
        {
            scanf("%c",&cmd);
            if(cmd == 'I')
            {
                gets(ccmd);
                if(No)
                    continue;
                facts++;
                if(sscanf(ccmd,"%d%d%d",&p,&q,&v) == 2)
                    v = q , q = n;
                if(!Union(p,q,v))
                {
                    No = true;
                    printf("The first %d facts are conflicting.\n",facts);
                }
            }
            else
            {
                M.clear();
                int ans = 0;
                scanf("%d",&k);
                while(k--)
                {
                    scanf("%d",&p);
                    if(No)
                        continue;
                    q = Root(p);            //can't exchange the order with the follow line
                    ans ^= val[p];
                    M[q]++;
                }
                getchar();
                if(No)
                    continue;
                bool Uncertain = false;
                for(map<int,int>::iterator it=M.begin();it!=M.end();it++)
                {
                    if(it->first != n && it->second & 1)
                    {
                        Uncertain = true;
                        break;
                    }
                }
                if(Uncertain)
                    puts("I don't know.");
                else
                    printf("%d\n",ans);
            }
        }
        puts("");
    }
    return 0;
}