시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 (추가 시간 없음) | 512 MB | 68 | 33 | 23 | 46.939% |
You are given a rooted tree where each vertex is labeled with a non-negative integer.
Define a Jumping Path of vertices to be a sequence of vertices v1, v2, ..., vk where vi is an ancestor of vj for all i < j. Note that vi is an ancestor of vi+1, but not necessarily the parent of vi+1 (hence the jumping part of a jumping path).
Compute two quantities:
The first line of input contains an integer n (1 ≤ n ≤ 106), which is the number of vertices in the tree. Vertices are numbered from 1 to n, with vertex 1 being the tree root.
Each of the next n lines contains an integer x (0 ≤ x ≤ 106), which are the labels of the vertices, in order.
Each of the next n − 1 lines contains an integer p (1 ≤ p ≤ n), which are the parents of nodes 2 through n, in order.
It is guaranteed that the vertices form a single tree, i.e., they are connected and acyclic.
Output a single line with two integers separated by a space.
The first integer is length of the longest jumping path where the labels of the vertices are nondecreasing. The second integer is the number of jumping paths of that length where the labels of the vertices are nondecreasing. As the second integer may be large, give its value modulo 11092019.
5 3 3 3 3 3 1 2 3 4
5 1
5 4 3 2 1 0 1 2 3 4
1 5
4 1 5 3 6 1 2 3
3 2
6 1 2 3 4 5 6 1 1 1 1 1
2 5