题解 | #叠积木#

一、把每堆积木看作一个集合，最下方的积木是集合的根节点
二、只需要维护集合中每个元素到根节点的距离d[x](这题和食物链那题基本相同）
三、还需要维护每个集合中元素的数量s[x]，目的是为了方便后面维护d[x]
四、find(x)函数返回x的祖宗节点，同时更新从x节点到祖宗节点路径上所有的节点d[x]
五、将a集合加入到b集合要做3件事
1、a节点的祖宗节点指向b，p[a]=b
2、更新d[a]，d[a]表示a到祖宗节点b的距离，所以d[a]等于原来b集合中元素的数量，即d[a]=s[b]
3、更新b集合内元素的数量s[b]，a集合加到b集合内之后,b集合元素总数量要加上s[a]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e4+10;
int p[N],d[N],s[N];//每堆积木为一个集合，最下方的积木是祖宗节点，s[i]表示每堆积木的数量
                   //d[x]表示x节点到祖宗节点的距离，即x下方有多少块木块
int q;
signed find(int x)//返回x的祖宗节点，同时更新x节点到祖宗节点路径上所有的d[x]
{
    if(p[x]!=x) 
    {
        int t=find(p[x]);
        d[x]+=d[p[x]];
        p[x]=t;
    }
    return p[x];
}
signed main()
{
    for(int i=1;i<=30000;i++)
    {
        p[i]=i;//初始每个积木表示一个集合
        s[i]=1;//初始每个集合内积木数量都是1
    }
    
    cin>>q;
    while(q--)
    {
        char op;
        cin>>op;
        if(op=='M')
        {
            int x,y;
            cin>>x>>y;//x所在的木块堆放到y所在集合堆上，即x所在木块堆全都加到y所在集合堆
            int a=find(x),b=find(y);//x的祖宗节点是a，y的祖宗节点是b
            p[a]=b;//a节点的祖宗节点指向b
            d[a]=s[b];//a集合加到b集合之后,b为祖宗节点,所以a节点到祖宗节点的距离就是a节点到b节点的距离
                      //a节点到b节点的距离大小等于b集合内元素数量,故d[a]=s[b]
            s[b]+=s[a];//同时a集合加到b集合内之后,b集合元素总数量要加上s[a]
        }
        else
        {
            int x;
            cin>>x;
            find(x);//d[x]可能并没有得到更新
            cout<<d[x]<<endl;
        }
    }
}