28112번 - 나무 타기 (Hard)

문제

이 문제는 나무 타기 문제와 $N$의 제한을 제외하고 같은 문제이다.

POSTECH 캠퍼스 내에는 정점이 $N$개인 루트가 있는 트리가 있다. 각 정점은 1ドル$번부터 $N$번까지의 번호를 가지며, $i$번째 노드의 부모 노드는 $P_i$번 노드이다. 루트의 경우 $P_i$ 값이 0ドル$이다.

POSCAT 부원들은 트리 알고리즘을 공부하기 위해 이 트리에서 나무 타기 놀이를 한다. 나무 타기 놀이란, 루트 노드에서 시작해 리프 방향으로 점프하는 것을 반복하며 리프 노드로 이동하는 놀이이다. 리프 노드란 자식 노드가 없는 노드를 말한다. 각 정점에는 정점의 강도 $A_i$가 주어져 있고, 이 강도 이상의 세기로 점프하게 되면 나무가 상할 수 있다. 따라서, 부원들은 $i$번째 정점에서 점프를 할 때, 거리가 1ドル$이상 $A_i$이하인 정점으로만 점프할 수 있다. 즉, 현재 위치한 정점이 $i$번 정점이라면 다음에 방문할 정점은 $i$번 정점을 루트로 하는 서브트리에 속하며 $i$번 정점과의 거리가 1ドル$ 이상 $A_i$ 이하인 정점이어야 한다.

만약 두 놀이의 방문한 정점들의 집합이 다르면, 두 놀이는 다른 놀이로 간주한다. 트리가 주어질 때, 서로 다른 나무 타기 놀이의 개수를 구해 보자. 정답이 클 수 있으므로 답을 998ドル,円 244,円 353$으로 나눈 나머지를 출력하여라.

입력

첫 번째 줄에 정점의 수 $N$이 주어진다. (1ドル\le N\le 10^6$)

두 번째 줄에 각 정점의 부모 노드를 나타내는 $N$개의 정수 $P_1,P_2,\ldots ,P_N$이 공백으로 구분되어 주어진다. 주어지는 그래프가 트리 구조임이 보장된다. (0ドル\leq P_i\leq N$)

세 번째 줄에 각 정점의 강도를 나타내는 $N$개의 정수 $A_1,A_2,\ldots ,A_N$이 공백으로 구분되어 주어진다. (0ドル\leq A_i\leq N-1$)

출력

서로 다른 나무 타기 놀이의 개수를 998ドル,円 244,円 353$으로 나눈 나머지를 출력한다.

제한

힌트