시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 512 MB 96 20 19 26.761%

문제

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