Source:

• 2021 KAIST RUN Spring Contest Problem H 「Fake Plastic Trees 2」.
• Petrozavodsk Winter 2022 Day 2: KOI TST + KAIST Contest Problem K 「Fake Plastic Trees 2」.
• XXII Open Cup, Grand Prix of Daejeon, Problem K 「Fake Plastic Trees 2」.

题目描述

给定一棵 $n$ 个点的树，点编号从 $1$ 到 $n$ 。每个点有一个非负权值 $a_i$。

你需要把树上的一些边删掉。你需要保证，删掉之后，每个连通块的权值之和在区间 $[L,R]$ 中。

给定非负整数 $K$ ，对于每个 $0\le i\le K$ ，判断能否恰好删去 $i$ 条边。

输入格式

第一行，一个正整数 $T$ ，表示数据组数，之后对于每组数据：

• 第一行四个非负整数 $n,K,L,R$。
• 第二行 $n$ 个非负整数 $a_1,\cdots,a_n$。
• 接下来 $n-1$ 行，每行两个正整数 $x,y$ ，表示树上的一条边。

输出格式

对于每组数据：

• 一行，一个长度为 $K+1$ 的字符串 $s$ ，其中 $s_i$ 在可以恰好删去 $i-1$ 条边时为 $\texttt{1}$ ，否则为 $\texttt 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

另有三组大样例位于题目附件。

数据范围

对于所有数据，$1\le T\le 1000$，$1\le n,\sum n\le 1000$，$0\le K\le \min(50,n-1)$，$0\le L\le R\le 10^{15}$，$0\le a_i\le 10^{15}$。