천체 관측소 동기화
골드 V의견: 0
천문대는 \(N\)개의 관측소(번호 \(1\)부터 \(N\))를 \(N-1\)개의 광케이블로 연결하여 하나로 이어진 트리 망을 구축했다. 각 광케이블에는 정수 지연 시간이 있다. 두 관측소 사이의 총 지연은 두 관측소를 잇는 유일한 경로상의 지연 시간 합이다.
관측 데이터를 동기화하려면, 총 지연이 짝수인 두 관측소 쌍의 개수가 필요하다. 서로 다른 두 관측소로 이루어진 순서 없는 쌍 \(\{u, v\}\) 중에서 둘 사이의 총 지연이 짝수인 것의 개수를 구하여라.
\(1 \le N \le 200{,}000\). 입력 그래프는 항상 하나로 연결된 트리이다.
첫째 줄에 관측소의 수 \(N\)이 주어진다. 이어 \(N-1\)개의 줄에 각각 세 정수 \(a\), \(b\), \(w\)가 주어지며, 관측소 \(a\)와 \(b\)가 지연 \(w\)인 케이블로 연결됨을 뜻한다 (\(1 \le w \le 10^9\)).
총 지연이 짝수인 관측소 쌍의 개수를 한 줄에 출력한다.
4
1 2 2
1 3 3
3 4 1
3각 관측소의 1번으로부터의 지연 합의 홀짝을 보면 1:짝, 2:짝, 3:홀, 4:짝 이다. 같은 홀짝끼리의 거리는 짝수이므로, 짝수 그룹 \(\{1,2,4\}\) 에서 \(\binom{3}{2}=3\) 쌍, 홀수 그룹 \(\{3\}\) 에서 0쌍, 합 3이 정답이다.
3
1 2 1
2 3 1
11과 3 사이의 지연은 \(1+1=2\) 로 짝수이고, 나머지 쌍 \(\{1,2\},\{2,3\}\) 은 홀수이다. 따라서 짝수 쌍은 1개이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
천체 관측소 동기화
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
천체 관측소 동기화