31724번 - Hyper Tree Problem 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 110 | 69 | 51 | 65.385% |
문제
$N$개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 $1$번부터 $N$번까지 번호가 붙어 있고, 트리를 구성하는 간선 또한 주어지는 순서대로 $1$번부터 $N-1$번까지 번호가 붙어 있다. 각 간선에는 $W_i$의 가중치가 존재한다.
다음 두 가지 유형의 질의가 합해서 $Q$개 주어진다. 2번 쿼리가 주어질 때마다, 답을 출력하는 프로그램을 작성하라.
1 e v: $e$번 간선의 가중치 $W_e$를 $W_e\ \And \ v$로 바꾼다. $\And$는 Bitwise AND 연산을 의미한다.2 n: $\sum_{i=1}^{N}{dist(n, i)}$를 출력한다. $dist(a, b)$는 $a$번 정점과 $b$번 정점 사이를 연결하는 유일한 경로에 포함된 간선 가중치를 모두 Bitwise OR 연산한 값이다. $a = b$인 경우에는 $dist(a, b) = 0$ 이다.
입력
첫째 줄에 $N$과 $Q$가 공백으로 구분되어 주어진다. $(2 \le N \le 300\ 000; 1 \le Q \le 300\ 000)$
다음 $N-1$개의 줄에는 트리의 간선 정보를 의미하는 $A_i, B_i, W_i$가 공백으로 구분되어 주어진다. 트리의 $i$번 간선이 연결하는 두 정점의 번호가 $A_i, B_i$이고, 간선의 초기 가중치는 $W_i$라는 의미이다. $(1 \le A_i < B_i \le N; 0 \le W_i < 2^{20})$
다음 $Q$개의 줄에는 아래와 같은 형식 중 하나로 쿼리에 대한 정보가 주어진다.
1 e v: $(1 \le e < N; 0 \le v < 2^{20})$2 n: $(1 \le n \le N)$
입력에서 주어지는 수는 모두 정수이고, 2번 쿼리가 적어도 하나 이상 주어짐이 보장된다.
출력
2번 쿼리의 수행 결과를 쿼리가 주어진 순서대로 한 줄에 하나씩 출력한다.
예제 입력 1
6 4 3 4 1 1 5 11 3 5 13 5 6 7 2 5 0 2 3 1 3 10 2 3 2 2
예제 출력 1
57 43 35
출처
University > UNIST-DGIST-POSTECH > 2024 UNIST-DGIST-POSTECH 연합 프로그래밍 경진대회 (2024 UDPC) > Senior Division H번
University > UNIST-DGIST-POSTECH > 2024 UNIST-DGIST-POSTECH 연합 프로그래밍 경진대회 (2024 UDPC) > Open Contest K번
- 문제를 만든 사람: bnb2011
- 문제를 검수한 사람: 99asdfg, andrew1010, hyperbolic, leo020630, lky7674, mjhmjh1104, nick832, slah007, tony9402, utilforever
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호