21770번 - Fake Plastic Trees 2 서브태스크다국어

문제

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점)

This subtask has an additional constraint:

• $N \le 10$

서브태스크 2 (24점)

This subtask has an additional constraint:

• $R \le 50$

서브태스크 3 (10점)

This subtask has an additional constraint:

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

서브태스크 4 (57점)

This subtask has no additional constraints.

힌트