이진 트리 그리기

시간 제한1초메모리 제한512 MB

요약

일부 노드의 x좌표가 고정된 이진 트리를 너비 V 격자에 규칙대로 그리는 방법의 수를 444449로 나눈 나머지로 구한다.

난이도: 어려움10점 중 8점
유형: 트리, 동적 계획법, 조합론, DFS
정답자: 아직 제출이 없습니다

문제

Bert 는 최근 이진 트리 (Binary Tree) 의 매력에 푹 빠져있다. 어떤 트리가 이진 트리이기 위해서는 각 노드의 자식이 최대 2개 이어야한다. 편의상 이진 트리 $T$ 의 노드는 $1$ 번부터 $N$ 번까지 번호가 붙어있으며, $i$ 번 노드의 왼쪽 자식은 $L\_i$ , 오른쪽 자식은 $R\_i$ 로 표현한다 -- 자식이 없을 경우 이 값은 0이 된다.

예를 들어 아래 트리는 $N = 3$ , $L = \[2, 0, 0]$ , $R = \[3, 0, 0]$ 인 경우를 나타내며 이 트리에서 루트는 1번 노드이다.

Bert 는 이진 트리 그리는 것을 좋아하는데, 우선 $V \ge N$ 인 적당히 큰 정수 $V$ 를 고정한 후, 아래 규칙에 따라 여러 가지 방법으로 그리는 것을 좋아한다. 편의상 노드 $i$ 의 정수 $x,y$ 좌표 값을 $(x\_i, y\_i)$ 라 하자.

$1 \le x\_i \le V$ 가 되도록 골라야 한다.
노드 $i$ 가 루트 노드라면 $y\_i = -1$ 이어야 한다.
노드 $p$ 가 노드 $i$ 의 부모라면 $y\_i = y\_p - 1$ 이어야 한다.
루트가 아닌 노드 $i$ 가 노드 $p$ 의 왼쪽 자식이라면 (즉 $L\_p = i$ ), 반드시 $x\_i \lt x\_p$ 이며 $i$ 의 모든 자식 및 자손 노드 $j$ 에 대해서도 $x\_j \lt x\_p$ 이어야 한다.
루트가 아닌 노드 $i$ 가 노드 $p$ 의 오른쪽 자식이라면 (즉 $R\_p = i$ ), 반드시 $x\_i \gt x\_p$ 이며 $i$ 의 모든 자식 및 자손 노드 $j$ 에 대해서도 $x\_j \gt x\_p$ 이어야 한다.

위 조건을 모두 만족하는 $N$ 개의 좌표값을 정했다면 이진 트리를 그릴 수 있다고 하며, 두 이진 트리 그림이 있을 때, 같은 노드의 $x$ 좌표 값이 다르면 두 그림은 다른 방법으로 그려진 것이라 하자 (위 규칙대로면 각 노드의 $y$ 좌표 값은 항상 같다). 위 예제의 경우 $V = 4$ 라면 아래와 같은 4가지 다른 방법으로 이진 트리를 그릴 수 있다.

Bert는 임의의 이진 트리가 주어졌을 때 위 방법을 모두 지키면서 몇 가지 다른 방법으로 이진 트리를 그릴 수 있는지 궁금해졌다. 그런데 이를 지켜보던 Alice는 그 문제는 너무 쉽다며, 새로운 문제를 주었다:

$N$ 개의 노드 중 일부 노드의 (0개일 수도 있고 $N$ 개일 수도 있음) $x$ 좌표를 고정한 후 위 규칙에 따라 그린다면 몇 가지 다른 방법으로 이진 트리를 그릴 수 있을까?
구체적으로 정수 배열 $A$ 가 주어지고, $A\_i = 0$ 인 경우 노드 $i$ 의 좌표는 고정되지 않은 경우이고 $A\_i \in \[1, V]$ 인 경우 노드 $i$ 의 좌표는 $x\_i = A\_i$ 가 되어야만 한다.

예를 들어 $A = \[0, 1, 0]$ 인 경우 앞서 살펴본 4개의 트리 중 $x\_2 = 1$ 을 만족하는 좌측 3개의 방법으로 트리를 그릴 수 있다.

같은 트리에 대하여 만약 $A = \[1, 0, 0]$ 인 경우, 조건을 만족하며 트리를 그릴 수 있는 방법이 없다 (앞서 살펴본바와 같이 4가지 방법으로 트리를 그릴 수 있지만, $x\_1 = 1$ 인 경우는 불가능하다).

입력으로 $N, V$ 와 세 개의 정수 배열 $A, L, R$ 이 주어졌을 때, Alice의 조건을 만족하며 이진 트리를 그릴 수 있는 방법의 수를 구해보자.

입력

입력 첫 줄에 테스트 케이스의 수 $T$ 가 주어진다.

각 테스트 케이스의 첫 줄에는 $N, V$ 가 공백으로 구분되어 주어진다. 둘째 줄에는 배열 $A$ 가, 셋째 줄에는 배열 $L$ 이, 네번째 줄에는 배열 $R$ 이 주어지며, 각 줄의 배열은 공백으로 구분되어 $N$ 개의 정수가 주어진다.

출력

각 테스트 케이스의 정답을 각 줄에 출력한다. 단, 이 수가 매우 클 수 있으므로 $444\\,449$ 로 나눈 나머지를 출력한다.

제한

$1 \le T \le 10$
$1 \le N \le 100\\,000$
$N \le V \le 1\\,000\\,000\\,000$
$1 \le i \le N$ 인 $i$ 에 대하여
- $0 \le A\_i \le V$
- $0 \le L\_i, R\_i \le N$
입력으로 주어지는 이진 트리는 $N$ 개의 노드, $N-1$ 개의 간선, 그리고 고유한 루트가 존재하며 싸이클이 없는 정상적인 이진 트리임이 보장된다.

예제1

예제 1

입력

6
3 4
0 0 0
2 0 0
3 0 0
3 4
1 0 0
2 0 0
3 0 0
3 4
0 1 0
2 0 0
3 0 0
5 7
0 4 0 0 0
0 3 0 0 0
2 4 0 5 0
5 10
0 5 0 0 0
0 3 0 0 0
2 4 0 5 0
6 10
0 0 3 6 0 8
2 3 0 0 6 0
0 5 4 0 0 0

예상 출력