특정한 정점들을 반드시 포함하는 최소 정점 트리 만들기 - list말고 반드시 set을 사용해야하는 경우

https://atcoder.jp/contests/abc368/tasks/abc368_d

D - Minimum Steiner Tree

 

 

1부터 n까지 번호를 가진 정점을 가진 트리에서 어떤 정점들을 제거할때, 특정한 정점 v1,v2,...,vk를 반드시 포함하게 하는 트리를 만들고 싶다면, 그러한 트리의 최소 정점 수는?

 

예를 들어 왼쪽 트리에서 1,3,5를 반드시 포함하는 트리를 만들고 싶을때, 4번, 6번, 7번을 제거하면 된다 

 

 

 

 

사실 테크닉에 감탄해서 복기하는거긴 한데 문제 해법도 어렵긴하다..

 

차수가 1이면서 v1,v2,..,vk가 아닌 정점을 생각해보자. 

 

차수가 1이라는 것은 트리에서 리프노드이다. 

 

위 예시를 보면 4,6,7이겠지

 

먼저 "구하고자 하는 정답인 최소 정점 트리"는 v1,v2,..,vk가 아닌 리프노드를 가지지 않는다.

 

만약 v1,v2,...vk가 아닌 리프 노드를 가진다고 한다면, 그러한 리프 노드를 제거하더라도, 

 

그러한 리프 노드만 사라지고 다른 정점은 사라지지 않으므로, 최소 정점에 모순이니 무조건 제거할 수가 있다.

 

역으로 v1,v2,..,vk가 아닌 리프노드를 가지지 않는 트리는, "구하고자 하는 정답인 최소 정점 트리"이다.

 

v1,v2,..,vk가 아닌 리프노드를 가지지 않는 어떤 임의의 트리 T와 

 

구하고자 하는 정답인, 최소 정점을 가지는 트리 T ' 에 대하여

 

T에서 T 와 T ' 의 교집합의 정점을 하나의 정점으로 축약시켜 얻은 트리가 T ''이라고 하자. 

 

T ''의 정점이 2개 이상이라면 T ''은 차수가 1인 정점을 2개 이상 가지는 것이며,

 

이 중 적어도 하나는 반드시 T의 v1,v2,...,vk가 아닌 리프노드가 되므로 가정에 모순이다.

 

따라서 T''의 정점은 반드시 1개이고 이것이 T와 T'의 교집합의 정점을 하나의 정점으로 축약시킨 그 정점이며

 

그러므로 T ⊂ T '이다. 

 

T ' 이 최소 정점인데 어떻게 T ⊂ T '인지? 헷갈리는데

 

"T에서 T 와 T ' 의 교집합의 정점을 하나의 정점으로 축약시켜 얻은 트리가 T '' "이걸 보면

 

T ''이 하나의 정점만 가진다면 이런 느낌임

 

 

 

그렇지만 T ' 은 최소 정점 트리이므로 T ' ⊂ T이다. 따라서 T = T '이다.

 

-------------------------------------------------------------------------------------------------------------------------------------------------

 

 

여기까지가 증명이긴한데 사실 직관적으로도 리프노드를 제거하면 트리가 안바뀌는데

 

v1,v2,...,vk가 아닌 노드 중에 리프노드가 아닌 어떤 노드를 제거한다면

 

제거해도 트리가 될려면 제거된 노드의 자식 노드들은 다 지워야함

 

그러다보니 제거되는 노드 A보다 v1,v2,...vk는 위쪽에 있어야하고 

 

그런데도 A가 리프는 아닐 수 있지 않느냐? 생각할 수 있는데 내가 하고 싶은 말은

 

v1,v2,..,vk가 아닌 리프노드들을 밑에서부터 위로 반복적으로 제거하자 이 말

 

 

 

 

리프노드 B,C를 제거하면 A가 리프노드가 되어 A도 제거해야하는

 

아무튼 결론

 

주어진 트리에서 v1,v2,..,vk가 아닌 리프노드를 밑에서부터 반복적으로 제거할 수 있을 때까지 제거하면 된다

 

그러면 트리를 구성하고 V = [v1,v2,...,vk]도 구성해준다

 

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

tree = [set() for _ in range(n+1)]

for _ in range(n-1):
    
    a,b = map(int,input().split())
    tree[a].add(b)
    tree[b].add(a)

V = list(map(int,input().split()))
V = {v:1 for v in V}

 

 

여기서 tree의 1,2,..,n번 노드와 연결된 노드들을 set()으로 관리했는데

 

list로 그동안 해왔는데 갑자기 set?

 

어차피 노드 번호 중복되는것도 없는데 굳이 set으로 해야함?

 

하지만 이건 확실한 이유가 있다

 

그 전에 먼저 이 트리의 리프노드들은 어떻게 찾을까? dfs를 돌아서 끝까지 가봐야하나?

 

그냥 1번부터 n번까지 돌아서 연결된 노드의 수가 1개인 노드를 찾으면 된다

 

leaf = []

for i in range(1,n+1):
    
    v = tree[i]
    
    if len(v) == 1:
        
        leaf.append(i)

 

 

그러면 리프 노드부터 제거해나갈거잖아

 

leaf에서 하나씩 돌아서 만약에 이 노드가 v1,v2,...,vk라면 넘어가고 v1,v,2...,vk가 아니라면 이제 제거해야할 대상인데

 

얘를 제거할려면 tree[v]에 있는 원소 vv를 먼저 빼야할거고, (리프노드니까 tree[v]에는 원소 vv밖에 없음)

 

그리고 핵심은 v를 제거할거니까 tree[vv]에 있는 수많은 원소 중 v를 제거해야한다

 

근데 만약에 tree = [[] for _ in range(n+1)]로 리스트로 관리해버리면 v를 제거하는데 O(N)인데

 

set()으로 관리하니까 v를 제거하는데 O(1)에 할 수 있다

 

set의 discard(v)는 v를 O(1)에 제거해준다

 

정점 수가 너무 많아서 이렇게 해야 시간초과를 안받음

 

for v in leaf:
    
    if V.get(v,0) == 1:
        
        continue
    
    vv = tree[v].pop()
    tree[vv].discard(v)

 

 

근데 tree[v]가 set이라서 tree[v][0]는 에러난다

 

set의 원소중 임의의 하나를 뺄려면 pop()인데 어차피 tree[v]에는 원소가 하나밖에 없어서 vv를 확실하게 뺄 수 있다

 

총 정점의 수는 n개인데 answer = n으로 저장해두고 리프 노드 1개씩 제거할때마다 answer -= 1을 해서 총 정점 수를 관리

 

그리고 v를 제거할때마다 아래 그래프에서도 보이지만, 새로운 정점이 새롭게 리프노드가 될 수 있다

 

그거는 v와 연결된 vv가 대상이 될 수 있는데 vv에 연결된 노드 수가 1개이면 vv가 새롭게 리프노드가 된다는 뜻이므로

 

vv를 leaf에 append해준다

 

 

 

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

tree = [set() for _ in range(n+1)]

for _ in range(n-1):
    
    a,b = map(int,input().split())
    tree[a].add(b)
    tree[b].add(a)

V = list(map(int,input().split()))
V = {v:1 for v in V}

leaf = []

for i in range(1,n+1):
    
    v = tree[i]
    
    if len(v) == 1:
        
        leaf.append(i)

answer = n

for v in leaf:
    
    if V.get(v,0) == 1:
        
        continue
    
    vv = tree[v].pop()
    tree[vv].discard(v)

    answer -= 1

    if len(tree[vv]) == 1:
        
        leaf.append(vv)
    
print(answer)

 

 

for v in leaf:

  

....

 

leaf.append(vv) 해도 신기하게 for v in leaf에 새로운 leaf가 반영되나봐??

 

당연히 에러날줄 알았는데