重铸华农荣光 我辈义不容辞

the eleventh day - disjoint set-food chain

This is really fucking difficult.I am still unable to do it

//用并查集来维护额外信息：d[]
//此外在运用“并查集”解题时要注意：并查集中每个集合时一个树的形式
#include<iostream>
using namespace std;

const int N=5*1e4+10;
int n,m;
//father数组，辅助数组-维护i节点到根节点的距离（因为初始每个节点都为根节点，所以距离初始都为0 ）
int p[N],d[N];

//路径的长度（高度），是需要自上而下加起来的，从根节点往下走,所以要先调用递归
int find(int x){
    if(p[x]!=x){
        int t=find(p[x]);//t暂时存p[x]“根”节点
        d[x]+=d[p[x]]; //find之后，p[x]存放p[x]到根节点之间的距离了；原d[x]为x到父节点之间的距离
        //路劲压缩优化
        p[x]=t; 
    }
    return p[x];
}

//此题：
//不管是否为同类还是异类，都把他放在同一集合中 ，即：只要知道了两个动物的关系就把他们放在集合里面去。这样，就可以间接得出各动物之间的关系
//核心：如何确定每个点之间的关系？=》如何确定每个点与根节点之间的关系？
//通过到根节点模上3的距离来判断：1表示可以吃根节点，2表示被根节点吃，3表示与根节点是同类
int main(){
    cin>>n>>m;

    for(int i=1;i<=n;i++)
        p[i]=i;

    int res=0;
    while(m--){
        int r,x,y; //r标识说法的种类
        cin>>r>>x>>y;

        if(x>n||y>n)  //三大“假条件”之二
            res++; 
        else{
            int px=find(x),py=find(y); //px和py都是根节点
            //r=1表示x和y是同类
            if(r==1){
                //px==py说明x和y已经在同一颗树上了
                //x和y若是同一种类，则他们到根节点的距离模3应该相等
                if(px==py && (d[x]-d[y])%3) res++;
                else if(px!=py){
                    //让x的祖宗节点指向y的祖宗节点
                    p[px]=py;
                    //定义px到py之间的距离：因为x和y是同类，所以x合并到y的集合中后，(d[x]+?)%3==d[y]%3 => d[y]-d[x]=?,其中？为x的祖宗节点px到y的祖宗节点的距离
                    d[px]=d[y]-d[x];
                }
            //r=2表示x吃y
            // =》x到根节点的距离比y到根节点的距离多1 =》(d[x]-d[y]-1)%3==0
            }else if(r==2){
                if(px==py && (d[x]-d[y]-1)%3) res++;
                else if(px!=py){  //x和y不在同一集合中
                    p[px]=py;
                    //因为x吃y，所以d[x]+?-d[y]-1==0 => ?=d[y]+1-d[x],其中？为d[px]
                    d[px]=d[y]+1-d[x];
                }
            }
        }
    }

    cout<<res;

    return 0;
}