LGP5092 【[USACO04OPEN]Cube Stacking】

题意：

编号为 $1\ldots n$ 的 $n$ ( $1 \leq n \leq 30000$ )个方块正放在地上，每个构成一个立方柱。

指令有两种：

移动（M）：将包含 X 的立方柱移动到包含 Y 的立方柱上。
统计（C）：统计含 X 的立方柱中，在 X 下方的方块数目。

分析：

对于每个方块 $x$ ,

$cnt_x$ 代表以 $x$ 为根结点的方块的个数，（即x是一幢方块的顶，问这幢方块一共有几个。）

$dis_x$ 表示 $x$ 到根节点的距离。(即x头上顶着多少个方块)

#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define per(i,x,y) for(int i=x;i>=y;i--)
#define rd(x) scanf("%d",&x);
typedef long long LL;
const int N=30010;
int n=30000;
int dis[N],fa[N],cnt[N];
int find(int x){
    if(x==fa[x]) return x;
    int f=find(fa[x]);
    dis[x]+=dis[fa[x]];
    fa[x]=f;
    return fa[x];
}
void merge(int x,int y){
    int fx=find(x),fy=find(y);
    if(fx==fy) return;
    fa[fy]=fx;
    dis[fy]=cnt[fx];
    cnt[fx]+=cnt[fy];
} 
int main(){
    for(int i=1;i<=n;i++) fa[i]=i,dis[i]=0,cnt[i]=1;
    int p;scanf("%d",&p);
    while(p--){
        char s[5];int x,y;
        scanf("%s",s);
        if(s[0]=='M'){
            scanf("%d%d",&x,&y);
            merge(x,y);
        } else {
            scanf("%d",&x);
            int fx=find(x);
            printf("%d\n",cnt[fx]-dis[x]-1);
        } 
    }
    return 0;
}

LGP2024 [NOI2001]食物链

如果x吃y 表示为x到y连边val=1
同类val=0

#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define per(i,x,y) for(int i=x;i>=y;i--)
#define rd(x) scanf("%d",&x);
typedef long long LL;
const int N=5e4+10;
int n,k,fa[N],dis[N];
int find(int x){
    if(x==fa[x]) return x;
    int f=find(fa[x]);
    dis[x]=(dis[x]+dis[fa[x]]+3)%3;
    fa[x]=f;return f;
}
void merge(int x,int y,int val){
    int fx=find(x),fy=find(y);
    fa[fy]=fx;dis[fy]=(dis[x]-dis[y]+val+3)%3;
}
int main(){
    rd(n);rd(k);int ans=0;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=k;i++){
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(x>n||y>n||op==2&&x==y){
            ans++;continue;
        }
        if(op==1){
            int fx=find(x),fy=find(y);
            if(fx!=fy){ merge(x,y,0);continue; }
            if(dis[x]==dis[y]) continue;
            else ans++;
        } else {
            int fx=find(x),fy=find(y);
            if(fx!=fy){ merge(x,y,1);continue; }
            if((dis[x]+1)%3==dis[y]) continue;
            else ans++;
        }
    }
    printf("%d\n",ans);
    return 0;
}