클래스 8에 속한 문제. sparse table, 혹은 LCA만 알고 있다면 간단한 케이스 분류로 쉽게 풀 수 있다.
한 트리 위의 노드 $a, b, c$를 생각하자. 두 노드 $x, y$에 대해 $x$에서 $y$로 가는 경로를 $P_{xy}$라고 적기로 하고, 이제 $P_{ab}, P_{bc}, P_{ac}$를 생각해 보자. 그럼 다음이 성립한다.
1. $P_{ab}, P_{bc}, P_{ac}$는 항상 유일하게 존재한다. 왜냐? 트리니까. 한 노드에서 다른 노드로 가는 경로가 여러 개 있다는 건 사이클이 있다는 소린데 그럼 트리가 아님.
2. 세 경로 $P_{ab}, P_{bc}, P_{ac}$에 모두 속해 있는 노드는 항상 한 개 이상 존재한다. 트리이기 때문. 만약 그런 노드가 없다면 $a \to b \to c \to a$ 사이클이 생기는데 그럼 트리가 아님.
이제 트리의 서브트리를 하나 갖고 오는데, 이 트리는
1. $a, b, c$를 모두 포함하고
2. 리프 노드가 3개 이하이고, 모든 리프 노드가 $a, b, c$ 중 하나
를 만족하는 녀석이다. 이게 이렇게 설명하니까 잘 안 와닿는데, 대충 설명하자면 트리에서 $a, b, c$ 부분을 가위로 찰칵찰칵 잘라서 $a, b, c$ 모두를 포함하고 있는 덩어리를 집은 것이다 ($a, b, c$가 서로의 부모 노드가 아닌 경우에만 먹히는 설명인데, 만약 그걸 캐치했다면 나중에 예외 케이스를 생각해봐야겠구나 하고 계획을 잡을 수 있겠다).
어쨌든 가지고 온 이 트리는 네 가지 형태로 분류할 수 있다.
1. dot : 세 노드가 같은 경우
2. linear: 두 노드가 같고 한 노드가 다른 경우
3. bent: 세 노드가 모두 서로 다르고, 세 노드가 한 경로 위에 놓인 경우. formal하게 표현하자면, 서로 다른 세 노드 $a, b, c$에 대하여 $\exists i, j, k \in \{a, b, c\}, i \neq j \neq k \wedge k \in P_{ij}$를 만족.
4. trigonal: otherwise.
화학의 분자 구조 이름에서 따 왔다. 꽤 그럴듯한데?
어쨌든 저 네 가지 경우에서 각각 외심을 찾아 보자면:
1. ㅋㅋ
2. 서로 다른 두 노드의 중점이다.
3. 없다.
4. 이 경우를 구하는 게 핵심이라면 핵심이다. 우선 외심이 존재한다고 치고 얘를 $o$라고 부르자. 그러면 $P_{ao}$의 길이와 $P_{bo}, P_{co}$의 길이가 서로 다 같아야 한다.
아까 전에 잠깐 했던 얘기를 다시 들고 오자. 세 경로 $P_{ab}, P_{bc}, P_{ac}$에 동시에 속해 있는 노드는 항상 한 개 이상 존재한다고 했다. trigonal 구조의 경우 그 노드가 딱 하나밖에 없는데(트리의 구조를 떠올려 보자! 항상 '삼거리' 노드가 딱 하나만 존재한다), 이 노드를 $t$라고 부르자.
$t$를 트리 위에서 움직여 $o$로 이동시키는 상황을 생각하자. 편의상 $t$와 $c$ 사이에 $o$가 있다고 하면, $t$를 $o$쪽으로 한 칸씩, $n$번 움직였을 때의 위치를 $t_n$이라고 했을 때 $P_{at_n}, P_{bt_n}, P_{ct_n}$의 길이는 각각 $|P_{at}| + n, |P_{bt}| + n, |P_{ct}| - n$으로 표현할 수 있다!
만약 $t_m$이 $o$와 같다고 하면, $|P_{at}| + m = |P_{bt}| + m = |P_{ct}| - m$이 성립하고, 따라서 $P_{at}$와 $P_{bt}$의 길이가 같아야 한다는 사실을 얻을 수 있다.
사실 괜히 엄밀하게 설명한다고 줄줄 적은 거지만 푸는 상황에선 그냥 어? 이거 대충 움직이니까 얘네 길이 같아야겠네? 하고 보면 된다.
아무튼 이제 외심이 존재할 경우 $|P_{at}| = |P_{bt}|$라는 사실을 얻었는데, 하나 더 해야 한다. 앞에서 $t$와 $c$ 사이에 외심이 존재할 것으로 가정했기 때문에, 정말로 그런 상황인지를 알아야 하겠다.
일단 $|P_{at}| = |P_{bt}|$만으로 외심으로 의심되는 노드를 구할 수는 있다. 외심의 정의에 따라 $a$/$b$와 $c$의 거리상 가운데 노드를 잡으면 된다. 그러고 나서 그 노드가 진짜로 조건을 만족하는지 체크하면 끝.
이걸 무지성 parent->parent->parent 도배로 구현하면 TLE고, LCA를 적용하면 시간 안에 들어온다.
언제나 sparse table은 [log][N]인거 잊지 말기! (cache hit...)