30239번 - 트리와 XOR 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 162 | 110 | 101 | 66.013% |
문제
정점이 $n$개인 트리가 주어진다. 각 정점에는 $1$부터 $n$까지의 번호가 붙어 있고, $i$번 정점에는 정수 $a_{i}$가 쓰여 있다. 당신은 원하는 만큼 시행을 하여 모든 $a_{i}$를 같게 만들어야 한다.
한 번의 시행에서 당신은 정점 $v$와 음이 아닌 정수 $c$를 선택한다. 그 다음 $v$를 루트로 하는 서브트리의 모든 정점 $i$에 대하여, $a_{i}$를 $a_{i}$를 $a_{i} \oplus c$로 바꾼다. $v$를 루트로 하는 서브트리의 크기를 $s$라 할 때, 이 시행의 비용은 $s \cdot c$이다. $\oplus$는 bitwise XOR을 의미한다.
$r$번 정점이 트리의 루트일 때 목표를 달성하기 위한 최소 비용을 $m_{r}$이라 하자. $m_{1}, m_{2}, \ldots, m_{n}$을 구하여라.
입력
각 입력은 여러 개의 테스트 케이스로 이루어져 있다. 첫 번째 줄에 테스트 케이스의 개수 $t$가 주어진다($1 \le t \le 10^{4}$). 다음 줄부터 각각의 테스트 케이스가 주어진다.
각각의 테스트 케이스의 첫 번째 줄에 정수 $n$이 주어진다 ($1 \le n \le 2 \cdot 10^{5}$).
두 번째 줄에 $n$개의 정수 $a_1, a_2, \ldots, a_n$가 주어진다 ($0 \le a_i < 2^{20}$).
다음 $n-1$개의 줄에 트리의 간선이 잇는 정점의 번호를 나타내는 두 정수 $u$와 $v$가 공백으로 구분되어 주어진다 ($1 \le u, v \le n$),
주어진 간선이 트리를 이룸이 보장된다.
모든 테스트 케이스에서 $n$의 총합은 $2 \cdot 10^{5}$를 넘지 않는다.
출력
각각의 테스트 케이스마다 $n$개의 정수 $m_1, m_2, \ldots, m_n$을 공백으로 구분하여 출력한다.
예제 입력 1
2 4 3 2 1 0 1 2 2 3 2 4 1 100
예제 출력 1
8 6 12 10 0
노트
첫 번째 테스트 케이스에서, 다음 방법으로 목표를 달성할 수 있다.
- 첫 번째 시행에서 $v=2$, $c=1$을 선택한다. 시행 후 $a=[3, 3, 0, 1]$이 된다. 이 시행의 비용은 $3$이다.
- 두 번째 시행에서 $v=3$, $c=3$을 선택한다. 시행 후 $a=[3, 3, 3, 1]$이 된다. 이 시행의 비용은 $3$이다.
- 세 번째 시행에서 $v=4$, $c=2$를 선택한다. 시행 후 $a=[3, 3, 3, 3]$이 된다. 이 시행의 비용은 $2$이다.
이 과정의 총 비용은 $3+3+2=8$이다. $8$ 미만의 비용으로 목표를 달성하는 방법이 없음을 증명할 수 있다.
$m_{2}$, $m_{3}$, $m_{4}$도 마찬가지로 찾을 수 있다.
두 번째 테스트 케이스에서, 정점이 하나이므로 목표가 이미 달성되었다.
출처
Contest > Codeforces > Codeforces Round 899 (Div. 2) D번
- 문제를 만든 사람: puppy
- 문제를 검수한 사람: kongum, silverwolf, qwerasdfzxcl, mjhmjh1104, mingyu331, lisifu, leinad2, koosaga, alex0211, kep1er07, jk410, jamesoh1201, gs20036, fs_edge, flappybird, benedict0724
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호