Almost union find (weighted union search)

The question ： Yes n Number , At first, each number is a separate set , The following three operations are given

1 p q ： take p and q Merge into a set

2 p q ： take p Put it in q In the collection

3 p ：  Output p The number of elements in the set and the sum of elements .

Ideas ： about 1 operation   If p q Different ancestors , that merge（p,q） that will do ; about 3 operation , Just find p The ancestors of the , Then output the number of elements in the set and the sum of the elements , about 2 operation , We can't merge directly p q , Because of this p Our children and grandchildren also belong to q in This is not in line with the meaning of the question , ad locum , We You need to open a new node , Make it a single collection , And let p Point to this node , such When we operate It's right This node performs operations , Without change The original p The location of , Let's define a Array idx【i】 It said i Pointed node . In this case take idx【i】 And q Merge , meanwhile stay p Delete from the collection of p This point is OK . See the code for details ：

#include<stdio.h>
#include<string.h>
#include<math.h>
#define inf 0x3f3f3f3f
#define LL long long
#include<algorithm>
using namespace std;
int f[100010],idx[100010],num[100010],sum[300010];
int n,m;
void init()
{
    for(int i=1; i<=100010; i++)
    {
        f[i]=i;
        idx[i]=i;
        num[i]=1;
        sum[i]=i;
    }
    return ;
}
int getf(int v)
{
    if(f[v]==v)
        return v;
    int s=getf(f[v]);
    sum[v]=sum[v]+sum[f[v]];
    num[v]=num[v]+num[f[v]];
    return f[v]=s;
}
void merge(int u,int v)
{
    int t1=getf(idx[u]);
    int t2=getf(idx[v]);
    if(t1!=t2)
    {
        f[t2]=t1;
        sum[t1]=sum[t1]+sum[t2];
        num[t1]=num[t1]+num[t2];
    }
    return ;
}
void build(int p)
{
    int k=++n;
    idx[p]=k;
    f[k]=k;
    sum[k]=p;
    num[k]=1;
}
int main()
{
    int x,p,q;
    while(~scanf("%d %d",&n,&m))
    {
        init();
        for(int i=0; i<m; i++)
        {
            scanf("%d",&x);
            if(x==1)
            {
                scanf("%d %d",&p,&q);
                int t1=getf(idx[p]);
                int t2=getf(idx[q]);
                if(t1!=t2)
                    merge(p,q);
            }
            else if(x==2)
            {
                scanf("%d %d",&p,&q);
                int t1=getf(idx[p]);
                int t2=getf(idx[q]);
                if(t1!=t2)
                {
                    int f=getf(idx[p]);
                    sum[f]=sum[f]-p;
                    num[f]--;
                    build(p);
                    merge(p,q);
                }
            }
            else
            {
                scanf("%d",&p);
                int t=getf(idx[p]);
                printf("%d %d\n",num[t],sum[t]);
            }
        }
    }
    return 0;
}