시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 81 | 45 | 13 | 43.333% |
상민이와 지수가 전쟁 시뮬레이션 게임을 한다. 게임에는 N개의 지역이 있으며, 각 지역은 전투력을 가지고 있다. 지역들은 N-1개의 길로 연결되어있으며, 연결된 지역 사이를 이동할 수 있다. 모든 지역이 하나의 방향 없는 트리구조를 이루고 있어 임의의 지역에서 다른 지역으로 언제나 이동할 수 있다.
게임 한 판은 다음과 같이 진행된다.
<그림 1> 지수의 세력 예시 (예제1)
각 세력의 전투력은 다음과 같이 계산된다.
$$\sum_{u\in\text{세력}} A_u\times(\max_{v\in\text{세력}}(dist(P, v)) - dist(P, u) + 1) $$
여기서 P는 플레이어가 각 세력의 요새 혹은 선봉으로 지정한 지역, dist(a,b)는 a 지역과 b 지역 간 거리이다.
예를들어, <그림 1> 에서 지수의 세력은 {(2) × 1} + {(3) × 2} + {(8 + 6 + 1) × 3} + {(2 + 7) × 4} + {(4) × 5} + {(5) × 6} = 139 의 전투력을 갖는다.
이 게임의 고인물인 지수는 게임에 버그가 있음을 알고 있다. 게임 내 전투력의 자료형이 unsigned int로 구현되어, 세력의 전투력이 232-1을 넘어가는 순간 오버플로우가 발생해 0부터 다시 시작하게 되는 것이다. 이 버그를 잘 이해하고 있는 지수는 버그를 적극 활용해 상민이로부터 대승을 거두고자 한다.
첫 줄에는 지역의 개수 N, 진행될 게임의 횟수 Q가 주어진다.
두 번째 줄부터 N-1 줄에 걸쳐 지역 간 길의 정보를 나타내는 u, v (1 ≤ u, v ≤ N) 가 주어진다. 이는 u번 지역과 v번 지역이 연결되어있다는 의미이다.
N+1번째 줄에는 각 지역의 전투력 Ai (1 ≤ i ≤ N) 가 1번 지역부터 N개에 걸쳐 차례로 주어진다.
N+2번째 줄부터 Q 줄에 걸쳐 각 판마다 상민이가 요새를 설치한 지역의 번호 x (1 ≤ x ≤ N) 가 주어진다.
Q 줄에 걸쳐 각 판마다 상민이가 요새를 설치한 지역의 번호가 x (1 ≤ x ≤ N) 일 때, 지수가 선봉을 지정하여 얻을 수 있는 "지수의 전투력 - 상민이의 전투력"
의 최댓값을 한 줄씩 출력한다.
10 3 1 2 2 3 3 4 3 5 4 6 5 7 5 8 8 9 9 10 0 5 4 2 7 8 6 1 3 2 1 2 5
139 99 -23
상민이가 1번 지역에 요새를 설치하면 지수는 2번 지역을 선봉으로 지정해 139의 전투력을 얻을 수 있다. 두 세력의 전투력의 차는 139 - 0 = 139 이다.
상민이가 5번 지역에 요새를 설치하면 지수는 어떤 지역을 선봉으로 지정해도 상민이를 이길 수 없다. 지수가 3번 지역을 선봉으로 지정하면 상민이는 57, 지수는 34의 전투력을 얻어 차이를 최소화할 수 있다.
6 2 1 2 1 3 1 4 1 5 1 6 2147483646 1 1 1 1 1 1 3
1 0
상민이가 1번 지역에 요새를 설치하면 지수는 어떤 지역을 선봉으로 지정해도 상민이를 이길 수 없는 것이 정상이지만, 오버플로우가 발생해 상민이의 전투력이 0이 되어 상민이를 이길 수 있다.
University > 아주대학교 > 2019 아주대학교 프로그래밍 경시대회 APC > Div.1 H번