带权并查集注意事项

食物链

#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`，因为它们在处理负数时的行为是不同的。