경로의 XOR
골드 I의견: 0
\(N\)개의 정점으로 이루어진 가중치 트리가 주어진다. 트리에서 서로 다른 두 정점 사이에는 유일한 경로가 존재한다.
각 질의 \(u\ v\)에 대해, 정점 \(u\)에서 정점 \(v\)로 가는 경로 위에 있는 모든 간선의 가중치를 XOR한 값을 출력하여라. \(u=v\)이면 경로에 간선이 없으므로 답은 \(0\)이다.
여기서 XOR(배타적 논리합, \(\oplus\))는 두 수를 이진법으로 나타냈을 때 각 자리를 비트 단위로 더한 뒤 \(2\)로 나눈 나머지를 취하는 연산이다.
\(1 \le N \le 100\,000\), \(1 \le Q \le 100\,000\), \(1 \le a, b, u, v \le N\), \(1 \le w \le 10^9\).
첫째 줄에 정점의 개수 \(N\)이 주어진다. 다음 \(N-1\)개의 줄에 간선의 정보 \(a\ b\ w\)가 주어진다 — 정점 \(a\)와 \(b\)를 잇는 가중치 \(w\)의 간선이다.
그 다음 줄에 질의의 개수 \(Q\)가 주어지고, 이어지는 \(Q\)개의 줄에 각 질의 \(u\ v\)가 주어진다.
각 질의마다 한 줄에, \(u\)에서 \(v\)로 가는 경로 위 간선들의 XOR 값을 출력한다.
5
1 2 6
2 3 5
2 4 3
1 5 10
4
3 5
4 3
1 1
5 4
9
6
0
15
\(3\to5\) 경로는 간선 \(5,6,10\)을 지나 \(5\oplus6\oplus10=9\). \(4\to3\)은 \(3\oplus5=6\). \(1\to1\)은 간선이 없어 \(0\). \(5\to4\)는 \(10\oplus6\oplus3=15\).
2
1 2 7
3
1 2
2 1
1 1
7
7
0
간선 하나뿐이라 \(1\to2\)는 \(7\), 같은 정점 질의는 \(0\).
골드 II
플래티넘 V막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
경로의 XOR
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
경로의 XOR