18189번 - 참 어려운 문제

N개의 정점으로 이루어진 루트 있는 트리가 있다. 모든 정점에는 1번부터 N번까지 번호가 붙어있다. 또한 i번 정점은 A_i번 색으로 칠해져 있다(1 ≤ i ≤ N).

이 트리에는 아주 특이한 성질이 있다. 색깔이 같은 두 정점을 고르면, 이 둘은 항상 조상-자식 관계가 아니다.

교준이는 이 트리의 구조는 알지만, 루트가 어떤 정점인지는 알지 못한다. 루트가 될 수 있는 정점을 모두 찾는 프로그램을 작성하시오.

첫 번째 줄에 정점의 개수를 의미하는 자연수 N이 주어진다.

두번째 줄에 정점의 색을 의미하는 N개의 자연수 A₁, ···, A_N가 사이에 공백을 두고 주어진다.

세번째 줄부터 (N-1)개의 줄에 걸쳐, (N-1)개의 간선의 정보가 주어진다. (i+2)번째 줄에는 i번째 간선의 정보를 나타내는 두 자연수 B_i와 C_i가 사이에 공백을 두고 주어진다(1 ≤ i < N).

i번째 간선은 B_i번 정점과 C_i번 정점을 서로 연결한다(1 ≤ i < N).

첫 번째 줄에 루트가 될 수 있는 정점의 개수를 출력한다.

두번째 줄에 루트가 될 수 있는 정점의 번호의 합을 출력한다.

세번째 줄에 루트가 될 수 있는 정점의 번호의 제곱의 합을 출력한다.

어떠한 정점도 루트가 될 수 없다면, 이들의 값은 전부 0임에 유의하라.

모든 입력 데이터는 다음 조건을 만족한다.

• 1 ≤ N ≤ 250,000
• 1 ≤ A_i ≤ N (1 ≤ i ≤ N)
• 1 ≤ B_i ≤ N (1 ≤ i < N)
• 1 ≤ C_i ≤ N (1 ≤ i < N)
• B_i ≠ C_i (1 ≤ i < N)