学步园

没注意只有一个case   不知道怎么就错了 -  -

带权并查集的"权"表示该节点与爸爸的关系

这题的关系有

0.儿子与爸爸是同类

1.儿子被爸爸是吃   -  -

2.儿子吃爸爸         =  =

为什么权要这样设?待会解释

所以每个节点多一个变量记录权

那两个不是父子关系的点之间的关系怎么表示呢?

为了解决这个问题  我们把每条指向父亲的边都看作向量!

eg:假如现在UFS是这样的

(节点,权)  (1,0)->(2,1)->(3,2)->(4,0)

那么可知:

1与2的关系是同类;

2被3吃;

3吃4;

4与4(自己)是同类

2与1是什么关系呢? 因为1->2的长度(权)是0 那么2->1的长度不也是0吗?  就是说2与1也是同类

3与2是什么关系?  同理  |3->2|=-1  怎么办?  权只有 0,1,2 啊 !  所以-1+3=2   即权为2  就是3吃吃2了

如果 a吃b b吃c c吃d 呢? 是多少怎么处理? 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 50010;

struct node
{
    int f,r;
}ani[maxn];

inline int mod(int a)
{
    a%=3;
    return a<0?a+3:a;
}

int ff(int x)
{
    int &f=ani[x].f,t=f;
    f=(f==x?x:ff(f));
    ani[x].r=mod(ani[x].r+ani[t].r);    ///BE CAREFUL!  Father is change!!
    return f;
}

int main()
{
    //freopen("a.in","r",stdin);
    int m,n;
    scanf("%d%d",&m,&n);
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        ani[i].f=i;
        ani[i].r=0;
    }
    for(int i=0;i<n;i++)
    {
        int o,a,b;
        scanf("%d%d%d",&o,&a,&b);
        o--;
        int ra=ff(a),rb=ff(b);  ///a to be father of b
        if(a>m||b>m)
            ans++;
        else if(o&&a==b)
            ans++;
        else
        {
            if(ra!=rb)
            {
                ani[rb].f=ra;
                ani[rb].r=mod(o+ani[a].r-ani[b].r);
            }
            else if(mod(ani[b].r-ani[a].r)!=o)
                ans++;
        }
    }
    printf("%d\n",ans);
    return 0;
}