시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 1024 MB 32 10 10 34.483%

문제

N개의 정점과 N-1개의 간선으로 구성되어 있으며, 어떤 두 정점을 고르더라도 두 정점을 잇는 유일한 하나의 경로가 존재하는 그래프를 트리라고 한다.

준영이와 성민이는 게임 폴 가이즈(Fall Guys)의 우승을 남겨두고 일대일 대결을 펼치게 되었다. 이 게임은 트리 형태의 게임판에서 진행되며, 준영이와 성민이가 각자 배정된 서로 다른 두 정점에 위치한 채로 시작된다. 게임은 서로 턴을 번갈아가며 진행된다. 자신의 턴이 오면, 자신이 위치한 정점과 인접한 정점으로 한 칸 이동해야 한다. 자신 혹은 상대방이 현재 위치하거나, 과거에 위치한 적이 있던 정점은 곧 게임 시스템에 의해 게임판의 바닥으로 떨어져 사라지기 때문에, 해당 정점으로는 이동할 수 없다. 만약, 이동할 수 없는 플레이어가 존재하면 그 플레이어의 턴은 무시하고 건너뛴다. 두 플레이어가 모두 이동할 수 없는 경우에는 게임이 종료된다. 각 플레이어는 한 칸 이동할 때마다 1점을 획득한다.

준영이와 성민이는 (자신의 점수 - 상대방의 점수)를 최대화하는 것이 목표이다. 준영이가 먼저 턴을 시작하고, 두 명 모두 항상 최선의 전략으로 게임을 플레이한다고 할 때, 게임이 끝난 뒤 (준영이의 점수 - 성민이의 점수)를 구하는 프로그램을 작성하시오.

위 그림은 예제 5를 표현한 것이다. 준영이는 노란색 정점들을, 성민이는 보라색 정점들을 밟는 것이 최선이다.

입력

첫째 줄에 게임판의 정점의 개수 N (2 ≤ N ≤ 200,000), 준영이가 배정된 정점 P, 성민이가 배정된 정점 Q (1 ≤ P, Q ≤ N, P ≠ Q)가 주어진다.

둘째 줄부터 N-1개의 줄에는 두 정수 Ai, Bi (1 ≤ Ai, BiN)가 주어진다. 이는 정점 AiBi를 잇는 간선이 존재함을 의미한다.

주어지는 입력은 트리 형태이다.

출력

준영이와 성민이가 (자신의 점수 - 상대방의 점수)를 최대화하는 방법으로 게임을 진행할 때, (준영이의 점수 - 성민이의 점수)를 출력하라.

예제 입력 1

2 1 2
1 2

예제 출력 1

0

예제 입력 2

4 1 2
1 2
2 3
4 3

예제 출력 2

-2

예제 입력 3

6 3 5
2 1
2 3
3 4
3 5
6 5

예제 출력 3

1

예제 입력 4

6 1 5
1 2
2 3
3 4
4 5
3 6

예제 출력 4

2

예제 입력 5

12 1 10
1 2
2 3
1 4
1 5
5 6
3 7
7 10
7 8
8 9
9 12
6 11

예제 출력 5

-1

출처

University > 인천대학교 > INU 코드페스티벌 2020 H번