<NOI2002>银河英雄传说の思路

emm并没有什么好说的.毕竟我这个蒟蒻都能yy出来

#include<cstring>
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int t,fa[30010],dis[30010],num[30010];
//dis距离num数量
char s;
int find(int n)
{
    if(fa[n]==n)return n;
    int father=fa[n];
    fa[n]=find(fa[n]);
    dis[n]+=dis[father];
    num[n]=num[fa[n]];
//更新一下
    return fa[n];
}
void he(int a,int b)//合并所以合并的英文貌似是merge
{
    int f1=find(a),f2=find(b);
    if(f1!=f2){
        fa[f1]=f2;
        dis[f1]=dis[f2]+num[f2];
        num[f1]+=num[f2];
        num[f2]=num[f1];
    }
}

int query(int a,int b)//查询
{
    int f1=find(a),f2=find(b);
    if(f1==f2){
        return abs(dis[a]-dis[b]);
    }
    return 0;
}

int main()
{
    int i,j;
    scanf("%d",&t);
    for(i=1;i<=30000;i++)
    {
        fa[i]=i;dis[i]=0;num[i]=1;
    }
    for(i=1;i<=t;i++)
    {
        cin>>s;
        int a,b;
        scanf("%d%d",&a,&b);
        if(s=='M')he(a,b);
        else printf("%d
",query(a,b)-1);
    } 
return 0;
}

 

没啦