Deblo
면접 대비시간 제한1초메모리 제한512 MB
노드마다 정수가 주어진 트리에서 두 노드 사이 경로의 값을 경로 위 노드 값의 XOR으로 정의할 때, 단일 노드 경로를 포함한 모든 경로 값의 합을 구합니다.
문제
약 30년 전, 어린 Krešo는 처음으로 전국 정보 올림피아드에 참가했다. 오늘날과 비슷하게, 대회 개회식은 참가자들에게 이 대회의 중요성을 동기 부여 메시지로 보여주려는 연사들의 발표로 이루어졌다. 청중은 몇 초마다 열광적으로 박수를 쳤지만, Krešo는 한 문장에 화가 났다. 연사 중 한 명이 승자가 누구든 자신에게는 Mirko와 Slavko가 모두 전국 대회의 승자이므로 논리 연산 OR보다 논리 연산 AND를 더 높이 평가한다고 주장했는데, 승자가 Mirko 또는 Slavko가 아니라 둘 다라는 뜻이었기 때문이다. Krešo는 화가 나서 일어나 청중에게 이것이 배타적 논리합(XOR)이라는 연산이라고 설명하기 시작했다. 강연을 마친 뒤, 그는 그 연사를 지목해 자신의 이해를 확인할 다음 과제를 내주었다.
N개의 노드로 이루어진 트리가 주어지고, 각 노드에는 값이 할당되어 있다. 트리 위의 경로의 값은 그 경로에 있는 모든 노드 값의 배타적 논리합으로 정의된다. 트리의 모든 경로, 즉 노드 하나만 포함하는 경로도 포함하여 모든 경로의 값의 합을 구하라.
30년 후, Krešo는 마침내 COCI 문제 출제자들을 설득해 이 문제를 한 라운드에 넣는 데 성공했다. 경쟁 프로그래밍의 미래에 대한 Krešo의 믿음을 되찾도록 도와달라.
입력
첫째 줄에는 트리의 노드 수를 나타내는 양의 정수 N (1 ≤ N ≤ 100 000)이 주어진다.
둘째 줄에는 공백으로 구분된 N개의 정수 vi (0 ≤ vi ≤ 3 000 000)가 주어지며, i번째 값은 i번째 노드의 값을 나타낸다.
다음 (N-1)개의 줄에는 두 수 aj와 bj (1 ≤ aj, bj ≤ N)가 주어지며, 이는 노드 aj와 bj 사이에 간선이 있음을 나타낸다.
출력
트리의 모든 경로에 대한 값의 합을 출력한다.
힌트
배타적 논리합(⊕)은 두 피연산자의 대응하는 각 비트 쌍에 대해 따로 적용되는 이항 연산으로, 결과의 어떤 비트는 두 피연산자 중 정확히 하나에서 그 비트가 1일 때에만 1이 된다.