27938번 - 트리 위의 세 사람 서브태스크

정점이 $N$개인 트리가 하나 있다. 각 정점에는 $1$부터 $N$까지의 정수 번호가 매겨져 있다. 루트는 $1$번 정점이다.

각 정점마다 사람들이 서 있는데, $i$번 정점에는 $A_i$명의 사람이 서 있다 $(1 \le i \le N)$. 또한, 양의 정수 $K$가 주어진다.

트리 상의 두 정점 $X$, $Y$에 대해 $lca(X,Y)$를 $X$와 $Y$의 최소 공통 조상, $dist(X,Y)$를 두 정점을 잇는 최단 경로에 있는 간선 개수로 정의한다.

이제 이 트리에서 서로 다른 사람 세 명을 고르자. 세 명은 모두 서로 다른 정점에 서 있어야 하고, 세 사람의 정점 번호의 집합을 $\{A, B, C\}$ 라고 했을 때 다음 조건을 만족해야 한다.

• $lca(A,B) = lca(A,C) = lca(B,C) = D \not\in \{A, B, C\}$
• $dist(A,D) + dist(B,D) + dist(C,D) = K$

그렇게 되도록 사람 세 명을 고르는 방법이 총 몇 가지 있는지 구하여라. 그 값이 클 수 있으니, $998\,244\,353$으로 나눈 나머지를 출력하여라.

첫 번째 줄에 줄에 트리의 정점 수 $N$, 문제에서 설명한 정수 $K$가 공백으로 구분되어 주어진다.

두 번째 줄에 $N-1$개의 정수 $P_2, P_3, \dots, P_N$이 공백으로 구분되어 주어진다. $P_i$는 $i$번 정점의 부모 정점 번호이다.

세 번째 줄에 $N$개의 정수 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다.

주어진 트리에서 세 사람을 조건에 맞게 고르는 방법의 수를 $998\,244\,353$으로 나눈 나머지를 출력한다.

• $4 \le N \le 500\,000$
• $3 \le K \le N-1$
• $1 \le P_i \le i - 1$ $(2 \le i \le N)$
• $1 \le A_i \le 998\,244\,352$ $(1 \le i \le N)$