20030번 - 트리와 쿼리 17 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB | 100 | 33 | 26 | 37.681% |
문제
$N$개의 정점으로 이루어진 트리가 있다. 정점은 1번부터 $N$번까지 번호가 매겨져 있고, 1번 정점은 루트이다. 각 정점 $i$에는 정수 $A[i]$가 저장되어 있다. 가장 처음에 $A[i]$는 0이다.
다음과 같은 쿼리를 수행해야 한다.
1 u: 정점 $u$를 루트로 하는 서브 트리의 모든 정점 $i$의 $A[i]$에 1을 더한다.2 u v: 정점 $u$에서 정점 $v$로 가는 유일한 최단 경로에 있는 모든 정점 $i$의 $A[i]$에 1을 더한다. $u$와 $v$는 같을 수도 있다.
각각의 쿼리를 수행한 후 $\sum_{y = 1}^{N} A[y] \times dist(x, y)$ 의 값을 가장 작게 만드는 정점 $x$를 출력한다. $dist(x, y)$ 는 $x$에서 $y$로 가는 경로에 존재하는 간선의 개수와 같다. 가능한 정점 x가 여러가지면, 루트에서 거리가 가장 가까운 정점을 출력한다. 그러한 정점은 항상 유일하다는 것을 증명할 수 있다.
입력
첫째 줄에 $N$이 주어진다. ($2 \le N \le 100\,000$)
다음 $N-1$개의 줄에는 트리의 간선이 주어진다. 각 줄은 공백으로 구분된 두 정수 $u$와 $v$가 주어지고, 정점 $u$와 정점 $v$를 연결하는 간선을 의미한다. ($1 \le u, v \le N, u \neq v$)
다음 줄에는 수행해야 하는 쿼리의 개수 $Q$가 주어진다. ($1 \le Q \le 100\,000$).
다음 $Q$개의 줄에는 쿼리가 한 줄에 하나씩 주어지며, 쿼리는 다음과 같은 형식이다.
1 u($1 \le u \le N$)2 u v($1 \le u, v \le N$)
출력
쿼리를 수행한 후 출력해야 하는 값을 Q개의 줄에 순서대로 출력한다.
예제 입력 1
7 1 6 1 7 7 3 3 2 7 5 5 4 4 1 2 1 4 1 6 2 6 7
예제 출력 1
2 7 7 1
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호