Public Judge

pjudge

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100

#21624. 【PR #2】背包

Statistics

给定一棵 $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$ 。

样例一

input

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

output

0111
0011
0000

样例二

见下发文件,该样例符合子任务 $3$ 的限制。

样例三

见下发文件,该样例符合子任务 $4$ 的限制。

样例四

见下发文件,该样例符合子任务 $5$ 的限制。

数据范围与提示

对于所有数据,$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}$ 。

子任务编号 特殊限制 分值
$1$ $\sum n\le 30$,$R\le 80$ $15$
$2$ $\sum n\le 100$,$R\le 200$ $15$
$3$ $\sum n\le 500$,$R-L\le 600$ $20$
$4$ 存在一个点的度数为 $n-1$ $15$
$5$ $ $ $35$

时间限制:$\texttt{3s}$

空间限制:$\texttt{1024MB}$