1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*n个动物 k句话 有一种循环a吃b 吃c c吃a 开始不知道n种动物关系是什么
两种询问：d=1 x y为同类  d=2 x吃y 判断假话条数（关键之违背之前的关系）
并查集可以很好解决的满足区间传递关系的区间合并问题，注意一般是多棵树*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int Max=50010*2;
int fat[Max],ran[Max];
void Init(int n)//初始化重要
{
    for(int i=0; i<=n; i++)
    {
        fat[i]=i;//初始化都是指向（看做）自己
        ran[i]=0;//0同类 1吃父节点 2被父节点吃
    }
    return;
}
int Find(int x)//找寻父节点+路径压缩
{
    if(x==fat[x])
        return fat[x];
    int y=Find(fat[x]);
        ran[x]=(ran[x]+ran[fat[x]])%3;//递归后从祖先节点向后到每个孩子来计算
    return fat[x]=y;//路径压缩
}
int Union(int typ,int x,int y)//区间并与查询
{
    int x1=Find(x);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX