409547: GYM103627 K Fake Plastic Trees 2

You are given a tree with $$$N$$$ vertices numbered 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. Then $$$T$$$ test cases follow, each following the given specification:

The first line of each test case contains four integers $$$N$$$, $$$K$$$, $$$L$$$, and $$$R$$$ ($$$1 \le N \le 1000$$$, $$$0 \le K \le \min(50, N - 1)$$$, $$$0 \le L \le R \le 10^{18}$$$).

The next line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$, where $$$A_i$$$ denotes the weight of vertex $$$i$$$ ($$$0 \le A_i \le 10^{18}$$$).

Each of the next $$$N-1$$$ lines contains two integers $$$x, y$$$, denoting the pair of vertices connected by an edge ($$$1 \le x, y \le N$$$, $$$x \neq y$$$). It is guaranteed that the given graph is a tree.

For all test cases, the sum of $$$N$$$ is at most $$$1000$$$.

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'.

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

0111
0011
0000