백준 17469 - 트리의 색깔과 쿼리 [Python]

https://www.acmicpc.net/problem/17469

17469번: 트리의 색깔과 쿼리

 

[사용한 알고리즘]

Smaller to Larger Technique

 

 

https://justicehui.github.io/medium-algorithm/2019/09/23/small-to-large/

이 글을 통해 공부했습니다

 

 

 

1. 쿼리를 뒤집는다.

2. 그러면 간선 제거를 간선 연결로 볼 수 있다. 그럼 엄청 쉬워진다

 

 

Union-Find를 통해 구현했고, 말 그대로 작은거를 큰거에 넣으면 됩니다.

import sys
 
input = sys.stdin.readline
 
p = [i for i in range(101010)]
 
 
def find(x):
    if x == p[x]:
        return x
    p[x] = find(p[x])
    return p[x]
 
 
def union(x, y):  # 작은거 x 큰거 y
    x = find(x)
    y = find(y)
    if len(c[y]) <= len(c[x]):
        x, y = y, x
    p[x] = y
    for i in c[x]:
        c[y].add(i)
    c[x].clear()
 
 
n, qs = map(int, input().split())
g = [0 for _ in range(101010)]
c = [set() for _ in range(101010)]
for i in range(2, n + 1):
    g[i] = int(input())
 
for i in range(1, n + 1):
    c[i].add(int(input()))
 
q = []
for i in range(n + qs - 1):
    a, b = map(int, input().split())
    q.append((a, b))
 
ans = []
q.reverse()
for a, b in q:
    if a == 1:
        union(b, g[b])
    else:
        ans.append(len(c[find(b)]))
 
ans.reverse()
for i in ans:
    print(i)