G Jumping Path
题号：NC224730
时间限制：C/C++/Rust/Pascal 10秒，其他语言20秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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 𝑣1, 𝑣2, … , 𝑣k where
vi is an ancestor of 𝑣j for all 𝑖 < 𝑗. Note that 𝑣i is an ancestor of 𝑣i+1, but not necessarily the parent of
𝑣i+1(hence the jumping part of a jumping path).

Compute two quantities:
1. The length (number of vertices) of the longest jumping path where the labels of the vertices are nondecreasing.
2. The number of jumping paths of that length where the labels of the vertices are nondecreasing.



输入描述:

The first line of input contains an integer 𝒏 (1 ≤ 𝒏 ≤ 106 ), which is the number of vertices in the tree.
Vertices are numbered from 1 to 𝒏, with vertex 1 being the tree root.

Each of the next 𝒏 lines contains an integer 𝒙 (0 ≤ 𝒙 ≤ 106 ), which are the labels of the vertices, in order.

Each of the next through 𝒏, in order. 𝒏 − 1 lines contains an integer 𝒑 (1 ≤ 𝒑 ≤ 𝒏), which are the parents of nodes 2
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.
示例1

输入

复制 
5 
3 
3 
3 
3 
3 
1 
2 
3 
4

输出

复制 
5 1

说明

示例2

输入

复制 
5 
4 
3 
2 
1 
0 
1 
2 
3 
4

输出

复制 
1 5

说明

示例3

输入

复制 
4 
1 
5 
3 
6 
1 
2 
3

输出

复制 
3 2

说明

示例4

输入

复制 
6 
1 
2 
3 
4 
5 
6 
1 
1 
1 
1 
1

输出

复制 
2 5

说明