[Meta Hacker Cup 2023] C. Wiki Race

A에서는 디버깅에, B에서는 코딩에 시간을 쓰는 바람에 C를 대회 중에 해결하지 못해 아쉽습니다. 하지만 991등으로 마무리하여 티셔츠는 받게 되었습니다. 대회를 잘 봤는지와 무관하게, C번 문제가 꽤 흥미로워서 풀이를 남겨 놓고자 합니다.

 

우선, 문제 상황은 다음과 같습니다.

• 정점이 $N$개인 트리가 주어집니다.
• 각 정점 $v$에는 $M_v$개의 문자열이 주어집니다.
• 트리를 여러 개의 경로로 분할하되, 각 경로에 문자열 $s$가 포함되게 할 수 있다면 $s$는 mutually-learned 합니다.
• mutually-learned 한 문자열의 개수를 세는 것이 문제입니다.
• 모든 TC에 대해 $N$의 합은 $3\cdot 10^6$을 넘지 않습니다.
• 모든 TC에 대해 $\sum M_v$의 합은 $8\cdot 10^6$을 넘지 않습니다.

 

생각 1: 문자열 종류가 하나인 경우를 먼저 고려합시다

특히 문자열끼리 독립적이기 때문에 이러한 접근이 꽤 도움이 될 것이라 유추할 수 있습니다.

 

생각 2: 문자열이 포함된 정점을 검은색, 포함되지 않은 정점을 하얀색으로 생각합시다

이러한 방법이 그래프 문제의 성질을 직관적으로 분석하기에 용이합니다.

 

관찰 1: 리프인 하얀색 정점은 검은색 정점을 만날 때까지 계속 올라가야 합니다

 

관찰 2: 검은색 정점은 올라가다 검은색 정점을 만나기 전까지 등장하는 하얀색 정점들을 경로에 포함시킬 수 있습니다

 

관찰 3: 리프는 올라가다 검은색 정점을 만나야 합니다

 

관찰 4: 리프만 검은색 정점까지 잘 연결시켜 주면, 나머지는 적당히 기존 경로에 포함시킬 수 있습니다

 

정리: 각 리프들을 가장 가까운 검은색 조상에 연결시키는데, 이 조상들이 서로 겹치지 않는다면, 그리고 오직 그럴때만, 가능합니다

 

해결해야 할 것: 문자열마다 리프 개수에 비례하는 시간이 걸린다

관찰 4에 의해 애초에 불가능한 경우를 쳐낼 수 있습니다. 검은색 정점의 개수가 리프의 개수보다 적은 상황 말이죠. (홀의 정리와 사뭇 비슷하기도 합니다)

그럼 검은색 정점의 개수가 리프의 개수 이상일 경우들에 대해서만 확인을 하게 되고, 이는 제곱근 분할의 논리로 amotized $O(\sum M)$하게 됩니다!!

 

풀이

리프들을 이용하여 virtual tree를 만들어 주면(트리 압축이라고도 부름) 쉽게 풀 수 있습니다.

 

하지만 조금 더 간단한 방법이 있습니다! 바로 색칠된 정점들을, 서브트리에 존재하는 리프의 수를 기준으로 정렬시켜서 하나씩 매칭시켜주는 것입니다. 서브트리에 존재하는 리프가 $0$개라면 매칭이 불가능하고, $1$개라면 거기에 매칭시킬 수 있습니다. $2$개 이상이라면 아무 리프에서 매칭시킨 뒤 서브트리 속 리프를 모두 이후 정점들의 매칭 후보에서 제거하면 됩니다.