[백준][Pyhton] 3780 네트워크 연결

union find의 변형. 특이한 점은 합칠때 부모가 아닌 해당 노드끼리 합치고

대신 해당 노드를 타고 올라가며 length를 갱신해줘야 된다는 점이다. 내 길이 = 부모의 길이들의 합.

import sys
input = sys.stdin.readline

def find(x):
    if parent[x]==x:
        return x
    # 부모쪽 length모두 갱신
    tmp = find(parent[x])
    # 내 length 갱신
    length[x] += length[parent[x]]
    # 부모값 저장
    parent[x] = tmp
    # 반환.
    return tmp

def union(a,b):
    length[a] = abs(a-b) % 1000
    parent[a] = b

for test in range(1,int(input())+1):
    N = int(input())
    parent = {i:i for i in range(1,N+1)}
    length = {i:0 for i in range(1,N+1)}
    while True:
        command = input().split()
        if command[0]=='E':
            find(int(command[1]))
            print(length[int(command[1])])
        elif command[0]=='I':
            union(int(command[1]),int(command[2]))
        else:
            break