Algorithm 문제
[백준] 13306 - 트리
노예2
2019. 6. 27. 13:13
https://www.acmicpc.net/problem/13306
13306번: 트리
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부모 정점을 나타내는 정수 a가 주어진다 (1 ≤ a ≤ N). 다음 (N-1)+Q개의 줄 중에서 N-1개는 (1)의 형태로, Q개는 (2)의 형태로 주어진다. (1) 두 정수 x와 b가 주어진다(x = 0, 2 ≤ b ≤ N). 이것은 b의
www.acmicpc.net
일반적인 방법으로 UNION-FIND TREE 를 사용할 경우 edge 삭제 후 부모 갱신 과정에서 시간초과가 발생한다. 삭제된 edge 의 하위에 있는 노드의 모든 부모를 갱신해야 하므로 오버헤드가 크다.
edge 를 추가하며 부모를 갱신할 경우, 앞선 경우에서의 오버헤드를 줄일 수 있다.
단, 결과가 반대로 얻으므로 저장 후, 역순으로 출력해야 한다.
<python 코드>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
import sys
inp = sys.stdin.readlines()
n, q = tuple(map(int, inp[0].split()))
parent = [i for i in range(n+1)]
result = []
for q in inp[n:][::-1]:
q = q.split()
if len(q) == 2:
parent[int(q[1])] = int(inp[int(q[1]) - 1])
else:
a, b = int(q[1]), int(q[2])
p_a, p_b = parent[a], parent[b]
while(True):
if parent[p_a] == p_a:
parent[a] = p_a
break
p_a = parent[p_a]
while(True):
if parent[p_b] == p_b:
parent[b] = p_b
break
p_b = parent[p_b]
if p_a == p_b:
result.append(True)
else:
result.append(False)
for re in result[::-1]:
if re:
print('YES')
else:
print('NO')
|
cs |