并查集_记录点到根的距离

https://scut.online/problem.php?id=78

题目描述
寓所共有n台服务器，服务器群可以看做是一些定根树组成的森林。一开始n台服务器互不相通且每台服务器均以自身为根服务器。帕秋莉会进行两种操作：
U u v w，表示将 v 结点的根服务器 root(v) 作为 u 结点的根服务器 root(u)的子结点接在 root(u) 上，并且 root(v) 到 root(u)的距离为 w。若 root(v) == root(u)，则不进行任何操作（注意，此时 root(v) 的所有子结点的根结点均变为root(u)，例如： root(v)会变为 root(u) ）；
C u，表示查询并返回u 到 root(u) 的距离。

输入格式
第一行为两个正整数n，m（1<=n<=100000，1<=m<=600000），表示服务器个数和操作次数；接下来m行，每行开头是一个字母‘U’或‘C’，表示操作种类：若开头字母为‘U’，则表示操作1。接下来会跟着三个数u，v，w（1 <= u, v <= n，1<=w<=100），表示将root(v)作为root(u)的子结点接在root(u)上，并且root(v)到root(u)的距离为w。若root(v) == root(u)，则不进行任何操作；若开头字母为‘C’，则表示操作2。接下来会跟着一个数u（1<=u<=n），表示查询结点u到其跟结点的距离。
输出格式
对于每个操作2，输出一行整数，表示查询的结点到其根结点的距离。
输入
5 6
C 4
U 4 2 51
C 2
U 3 1 2
U 3 4 6
C 2
输出
0
51
57

#include<stdio.h>
#include <string.h>
using namespace std;
#define maxn 100010
int fa[maxn];
int dis[maxn];
int father(int u)
{
    if(u==fa[u]) return u;
    int root=father(fa[u]);
    dis[u]=dis[u]+dis[fa[u]];
    return fa[u]=root;
}
void connect(int u,int v,int w)
{
    int fu=father(u);
    int fv=father(v);
    if(fu==fv) return ;
    fa[fu]=fv;
    dis[fu]=w;
}
int main()
{
   int n,m,u,v,w;
   scanf("%d%d",&n,&m);
   for(int i=1;i<=n;i++)
   {
       fa[i]=i;
       dis[i]=0;
   } 
    char s;
    getchar();
   for(int i=1;i<=m;i++)
   {
       s=getchar();
       if(s=='C')
       {
           scanf("%d",&u);
            father(u);
           printf("%d\n",dis[u]);
       }
       else
        {
            scanf("%d%d%d",&u,&v,&w);
            connect(v,u,w);
        }
        getchar();
   }
}