시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 512 MB 73 13 12 27.273%

문제

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

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

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

입력

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

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

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

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

출력

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

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

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

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

제한

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

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

예제 입력 1

6
3 2 4 1 4 3
1 2
2 3
2 5
2 6
3 4

예제 출력 1

1
2
4


 

예제 입력 2

6
1 2 1 1 3 3
1 2
2 3
2 5
2 6
3 4

예제 출력 2

0
0
0


 

출처

High School > 경기과학고등학교 > 나는코더다 2019 송년대회 E번

  • 데이터를 만든 사람: sebinkim
  • 문제를 만든 사람: yclock