keddad

Окей, в итоговой версии я избавился от рекурсии, типизации и Arrayев. Основной профит получил от рекурсии, конечно. Этого не хватило для решения задачи, но код заметно ускорился.

n, m = map(int, input().split())

parent, weight, rank = [-1 for _ in range(n)], [0 for _ in range(n)], [1 for _ in range(n)]


def find_set(v):
    while parent[v] != -1 and parent[v] != v:
        parent[v] = parent[parent[v]]
        weight[parent[v]] += weight[v]
        weight[v] = 0
        v = parent[v]
    if parent[v] == -1:
        parent[v] = v
    return v


def union_sets(a, b, cost):
    a = find_set(a)
    b = find_set(b)
    if a != b:
        if rank[a] < rank[b]:
            a, b = b, a
        parent[b] = a
        weight[a] += cost
        weight[a] += weight[b]
        weight[b] = 0
        if rank[a] == rank[b]:
            rank[a] += 1
    else:
        weight[a] += cost


def main():
    with open("input.txt", "r") as inp:
        with open("output.txt", "w") as out:
            inp.__next__()
            for line in inp:
                st = line.split()
                if len(st) != 4:
                    out.write(str(weight[find_set(int(st[1]) - 1)]) + "\n")
                else:
                    union_sets(int(st[1]) - 1, int(st[2]) - 1, int(st[3]))


main()