题解 P2024 【[NOI2001]食物链】

没有看懂楼下任何一个大佬对合并操作的分析

（一定是我太菜了QwQ）

于是自己推了推，发现用“数学的语言”很好懂。（为什么其他题解都把简单的东西讲得特别详细啊啊啊）

Method：带权并查集不解释。

对合并并查集操作的解释：

对于第二种操作，判完合法以后，就一定知道f[x]一定是x那一个并查集的根节点了（因为进行了GetFather操作路径压缩），那么f[x]的d肯定为0。
d值其实可以理解为这个是什么生物（在默认根节点为0号生物时）。
但现在它要接到y上去，又因为我们规定0吃2，2吃1，1吃0，且此时x吃y为合法，不妨用real(x)表示x真正是什么生物。
所以（以下均省略取模）可得real(x)=real(y)+1，那么f[x]和f[y]的距离就有关系real(f[x])+d[x]=real(f[y])+d[y]+1。
合并得real(f[x])-real(f[y])=d[y]-d[x]+1。
将根节点接到y的下面，就非常好办了。
第一种操作同理，只是不加1。

至于其他的地方，其他题解已经讲得非常清楚了，这里就不再赘述。
还是放一下代码吧。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,k;
int f[50001],d[50001];
int Find(int x)
{
    if(x==f[x]) return x;
    int X=f[x];
    f[x]=Find(f[x]);
    d[x]=(d[X]+d[x])%3;
    return f[x];
}
int main()
{
    int opt,x,y,ans=0;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++) f[i]=i,d[i]=0;
    for(int i=1;i<=k;i++)
    {
        scanf("%d %d %d",&opt,&x,&y);
        if(((--opt)&&x==y)||(x>n||y>n)) {ans++;continue;}
        if(opt)
        {
            if(Find(x)==Find(y))
                {if(d[x]!=(d[y]+1)%3) ans++;}
            else
            {
                d[f[x]]=(d[y]-d[x]+1+3)%3;
                f[f[x]]=f[y];
            }
        }
        else
        {
            if(Find(x)==Find(y))
                {if(d[x]!=d[y]) ans++;}
            else
            {
                d[f[x]]=(d[y]-d[x]+3)%3;
                f[f[x]]=f[y];
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

可以通过所有数据。