带权并查集注意事项

食物链

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int p[N],d[N];
int find(int x)
{
    if(p[x]!=x){
        int root=find(p[x]);
        d[x]+=d[p[x]];
        p[x]=root;
    }
    return p[x];
}
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)p[i]=i;
    int ans=0;
    while(k--)
    {
        int op,a,b;
        cin>>op>>a>>b;
        int pa=find(a),pb=find(b);
        if(a>n||b>n){
            ans++;
            continue;
        }
        if(op==1)
        {
            // if(pa==pb&&((d[a]-d[b])%3+3)%3!=0)ans++;
            if(pa==pb&&abs(d[a]-d[b])%3!=0)ans++;
            if(pa!=pb){
                p[pa]=pb;
                d[pa]=d[b]-d[a];
            }
        }
        else {
            // if(pa==pb&&((d[a]-d[b])%3+3)%3!=1)ans++;
            if(pa==pb&&abs(d[a]-d[b])%3!=1)ans++;
            if(pa!=pb){
                p[pa]=pb;
                d[pa]=d[b]-d[a]+1;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

让我们再次分析这两个表达式：`(d[a]-d[b])%3+3)%3!=1` 和 `abs(d[a]-d[b])%3!=1`。

首先，我们来看 `(d[a]-d[b])%3+3)%3!=1` 这个表达式。这个表达式的目的是在 `d[a]` 和 `d[b]` 的差值模3的基础上加3，然后再对3取模，以确保结果是非负的。这样做的原因是，当 `d[a]-d[b]` 为负数时，直接对3取模可能会得到一个负数，而加上3可以确保结果在0到2的范围内。但是，由于模运算 `%` 本身就会返回一个非负的余数，所以实际上这个操作是多余的。

现在，我们来看 `abs(d[a]-d[b])%3!=1` 这个表达式。这个表达式首先计算 `d[a]` 和 `d[b]` 的绝对差值，然后对3取模。如果 `d[a]` 和 `d[b]` 的差值是负数，那么 `abs` 函数会将其变为正数，然后对3取模。

关键的区别在于，`(d[a]-d[b])%3+3)%3!=1` 这个表达式在 `d[a]-d[b]` 为负数时，会得到一个与 `d[a]-d[b]` 模3相同的结果，而 `abs(d[a]-d[b])%3!=1` 这个表达式会得到 `d[a]-d[b]` 的绝对值模3的结果。

例如，如果 `d[a]-d[b] = -1`，那么：
- `(d[a]-d[b])%3+3)%3 = (-1)%3+3)%3 = 2%3 = 2`
- `abs(d[a]-d[b])%3 = abs(-1)%3 = 1%3 = 1`

在这种情况下，`(d[a]-d[b])%3+3)%3!=1` 会检查 `2!=1`，这是正确的。但是，`abs(d[a]-d[b])%3!=1` 会检查 `1!=1`，这是错误的。

因此，`(d[a]-d[b])%3+3)%3!=1` 不能写成 `abs(d[a]-d[b])%3!=1`，因为它们在处理负数时的行为是不同的。