테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 트리 게임 ======

===== 풀이 =====
  * A가 B를 잡을 수 있는 경우는, A와 B가 인접해있어서 첫수에 A가 B를 잡을수 있는 경우와, B가 막다른 길에 몰려있어서 A가 다가올때 B가 반대쪽으로 도망갈 수가 없는 경우, 이렇게 크게 두가지 뿐이다.
  * 정확한 설명은 [[https://teferi.net/_media/ps/kupc2025.pdf|에디토리얼]]에 이미 다 나와있으니 생략.
  * 다만 에디토리얼에는 케이스는 잘 설명되어있지만, 구현방법은 빠져있다. 에디토리얼의 설명 기준으로 구현방법을 설명하면
  * 두 플레이어의 거리가 1인 경우는, 하나의 엣지의 양 끝에 플레이어가 있는 경우이다. 즉 {엣지의 수} * 2 = (N-1)*2 이다
  * B가 갈 수 있는 b의 위치가 하나인 경우는, B에 인접한 노드들 중에서, 차수가 2 이상인 노드가 1개뿐일 때이다. 유일하게 차수가 2 이상인 노드가 b가 된다
    * b의 차수가 2보다 크다면, 가능한 c의 위치가 여러개이다. b의 차수가 2라면, 가능한 c의 위치가 1가지.
    * 이 경우에, A는 첫수에 b로 움직이면 B를 잡을수 있으므로, A의 가능한 위치는 {b의 차수} - 1 가지이다, 1을 빼는 이유는, 처음 B의 위치를 제외하기 위해서이다.
  * 가능한 c의 위치가 여러가지라면, b에서 거리가 1인 노드의 개수를 세면 된다. 이것은 {b의 차수} - 1 이다. 1을 빼는 이유는, 처음 B가 있던 노드는 제외해야 하기 때문이다
  * 가능한 c의 위치가 1가지라면, 두번 이동해서 c로 갈수 있는 노드의 개수를 세어야 한다. c에서 거리가 2인 노드의 개수를 세는 것은 O(E)가 걸리기 때문에, 매번 계산하면 시간초과가 생긴다. 미리 각 노드별로 거리가 2인 노드의 개수를 전처리해두는 것이 필요하다.
    * 여기서 최종적으로 답에 더해줘야 할것은 {c에서 거리가 2인 노드의 개수} 이다. 처음 B가 있던 노드는 제외하고, 대신 c의 위치를 포함시킨다.
  * 모든 노드에 대해서 거리가 2인 노드의 개수를 세는 것은 O(E). 모든 노드에 대해서 갈수있는 b의 위치가 하나인지 세는 것도 O(E). 총 시간복잡도는 O(E)=O(N)


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 34769. 트리 게임".

- Problem link: https://www.acmicpc.net/problem/34769
- Solution link: http://www.teferi.net/ps/problems/boj/34769

Tags: [tree]
"""

from teflib import tree as ttree


def main():
    N, tree = ttree.from_input()

    dist_2_node_counts = []
    for neighbors in tree:
        count = 0
        for v in neighbors:
            count += len(tree[v]) - 1
        dist_2_node_counts.append(count)

    answer = (N - 1) * 2
    for u, neighbors in enumerate(tree):
        v_cands = [v for v in neighbors if len(tree[v]) > 1]
        if len(v_cands) > 1:
            continue
        neighbor_v = tree[v_cands[0]]
        if len(neighbor_v) == 2:
            w1, w2 = neighbor_v
            w = w1 + w2 - u
            answer += dist_2_node_counts[w]
        else:
            answer += len(neighbor_v) - 1

    print(answer)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:플래티넘_3}}