문제
제노는 생일 파티를 열 예정이다. 파티에는 그가 사장으로 있는 회사의 직원들 중 몇몇을 초대하기로 했다. 제노를 포함하여 회사의 직원들은 1번부터 N번까지 고유한 사원번호를 갖고 있으며 각 사원들은 어떤 타입의 농담을 하는데 그 농담 타입을 Vi 로 나타낸다. 또한 제노를 제외하고 모든 사원은 정확히 한 명의 직접적인 상사가 있다.
제노는 회사의 사장이기 때문에 상사가 없으며 사원번호도 1번이다. 그리고 모든 사원의 직접적이거나 간접적인 상사이다.
생일 파티에 참석하는 모든 사람의 농담 타입들을 모아 농담 세트를 구성하는데 각각의 직원은 다음과 같은 규칙을 따라야 한다.
- 생일 파티에 같은 타입의 농담을 하는 사람이 두 명 이상일 수 없다.
- 제노를 제외하고 직접적인 상사가 초대되지 않는 직원은 초대될 수 없다.
- 어떤 사원 X가 파티에 참석한 모든 그의 직간접적인 부하 직원들과 함께 농담 세트를 연속적인 번호들로 구성할 수 없다면 초대될 수 없다.
인접한 원소들을 오름차순으로 정렬했을 때 1씩 증가하는 상태라면 연속적이라고 할 수 있다. 예를 들면 (3, 1, 2), (5, 1, 2, 4, 3) 등이 있다.
제노는 사원정보가 주어졌을 때 제약사항을 만족하는 얼마나 많은 서로 다른 농담 세트가 있는지 알고 싶다. 이를 구하는 프로그램을 작성해 보자.
입력 예 1에서 서로 다른 농담 세트는 {2}, {2, 3}, {2, 3, 4}, {1, 2, 3, 4}, {1, 2}, {1, 2, 3} 이다.
입력 예 2에서 서로 다른 농담 세트는 {3}, {3, 4}, {3, 4, 5}이다. {4, 6}은 연속된 수가 아니므로 가능한 경우의 수에 포함 될 수 없다.
입력 예 3에서 서로 다른 농담 세트는 {5}, {4, 5}, {3, 4, 5}, {2, 3, 4, 5}, {1, 2, 3, 4, 5}, {5, 6}, {4, 5, 6}, {3, 4, 5, 6}, {2, 3, 4, 5, 6}, {1, 2, 3, 4, 5, 6}이다.
입력
첫 번째 행에 N (1 ≤ N ≤ 10,000)이 입력된다. 두 번째 행에 i번째 사람의 농담의 유형 Vi( 1 ≤ Vi ≤ 100)가 N개 입력된다. 다음 N-1개의 행에 두 정수 A, B(1 ≤ A, B ≤ N)가 입력되는데 A는 B의 직접상사라는 의미이다.
출력
위 제약사항을 따르는 서로 다른 농담 세트의 수를 한 행에 출력한다.
예제1
4
2134
12
13
34
6
예제2
4
3456
12
13
24
3
예제3
6
536421
12
13
14
25
56
10