나무 타기 (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 \le P_i \le N$)

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

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