시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 1024 MB53161433.333%

## 문제

You are given a tree with $N$ vertices. Vertices are indexed from $1$ to $N$. The tree is vertex-weighted. In other words, each vertex of the tree is assigned a nonnegative integer weight.

We will delete some edges from the tree. After the deletion, for each connected component, the sum of vertex weights should be in the range $[L, R]$.

For all integers $0 \le i \le K$, determine if we can achieve this goal by deleting exactly $i$ edges.

## 입력

The first line contains a single integer $T$, the number of test cases. $T$ test cases follow, each following the given specification:

The first line contains four integers $N$, $K$, $L$, and $R$.

The next line contains $N$ integers $A_1, A_2, \ldots, A_N$, where $A_i$ denotes the weight of vertex $i$.

The next $N-1$ lines contain two integers $x, y$, denoting the pair of vertices connected by an edge.

## 출력

For each test case, output a binary string of length $K + 1$. The $i$-th character should be 1 if it is possible to achieve the desired goal by deleting exactly $i-1$ edges. Otherwise, the $i$-th character should be 0.

## 제한

• $1 \le N \le 1\,000$
• $0 \le K \le \min(50, N - 1)$
• $0 \le L \le R \le 10^{18}$
• $0 \le A_i \le 10^{18}$
• $1 \le x, y \le N$
• $x \neq y$
• The given graph is a tree.
• For all test cases, the sum of $N$ is at most $1\,000$.

## 서브태스크 1 (9점)

• $N \le 10$

## 서브태스크 2 (24점)

• $R \le 50$

## 서브태스크 3 (10점)

• $y = x + 1$ for all edges in the tree.

## 예제 입력 1

3
4 3 1 2
1 1 1 1
1 2
2 3
3 4
4 3 1 2
1 1 1 1
1 2
1 3
1 4
4 3 0 0
1 1 1 1
1 2
1 3
1 4


## 예제 출력 1

0111
0011
0000


## 채점 및 기타 정보

• 예제는 채점하지 않는다.