P2024 [NOI2001] 食物链
带权并查集。
我们维护每个点到根的距离，为 \(0\) 表示同类，为 \(1\) 表示吃根，\(2\) 表示被根吃。
判断合法只需要将 \(d_u,d_v\) 作差即可。
连接时可以 \(fa_u\rightarrow v\)，距离根据定义：
更新距离：路径压缩时，先临时存储父节点，find 一下（如果反了，就没有更新父节点前更新子节点，会导致错误），然后根据 \(dis[u][v]+dis[v][rt]=dis[u][rt]\)，累加父亲的距离（旧的）。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
#define Wh while
#define add(a,b) (a+=b)>=mod&&(a-=mod)
#define sub(a,b) (a-=b)<0&&(a+=mod)
const int N=50010,mod=3;
int n,k,f[N],d[N],ans;
int find(int x){
if(f[x]==x)return x;
int pa=f[x];
f[x]=find(f[x]);
d[x]+=d[pa];
return f[x];
}
void edge(int a,int b,int v){
if(a>n||b>n){
++ans;
return;
}
int ra=find(a),rb=find(b);
if(ra==rb)
ans+=(v+d[b])%mod!=d[a]%mod;
else{
f[ra]=b;
d[ra]=((v-d[a])%mod+mod)%mod;
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
E(i, n)f[i]=i;
W(k){
int op,a,b;
cin>>op>>a>>b;
edge(a,b,op-1);
}
cout<<ans;
return 0;
}