참 어려운 문제

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

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

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

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

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

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

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

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

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

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

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

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

• 1 ≤ N ≤ 250,000
• 1 ≤ Ai ≤ N (1 ≤ i ≤ N)
• 1 ≤ Bi ≤ N (1 ≤ i < N)
• 1 ≤ Ci ≤ N (1 ≤ i < N)
• Bi ≠ Ci (1 ≤ i < N)