#P9686. Fake Plastic Trees 2

    ID: 6309 传统题 3000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF2900省选/NOI-树上背包有限候选集缩减子树合并剪除无效容量

Fake Plastic Trees 2

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

题目描述

给定一棵 nn 个点的树,点编号从 11 到 nn 。每个点有一个非负权值 aia_i。

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

给定非负整数 KK ,对于每个 0≤i≤K0\le i\le K ,判断能否恰好删去 ii 条边。

输入格式

第一行,一个正整数 TT ,表示数据组数,之后对于每组数据:

  • 第一行四个非负整数 n,K,L,Rn,K,L,R。
  • 第二行 nn 个非负整数 a1,⋯ ,ana_1,\cdots,a_n。
  • 接下来 n−1n-1 行,每行两个正整数 x,yx,y ,表示树上的一条边。

输出格式

对于每组数据:

  • 一行,一个长度为 K+1K+1 的字符串 ss ,其中 sis_i 在可以恰好删去 i−1i-1 条边时为 1\texttt{1} ,否则为 0\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≤T≤10001\le T\le 1000,1≤n,∑n≤10001\le n,\sum n\le 1000,0≤K≤min⁡(50,n−1)0\le K\le \min(50,n-1),0≤L≤R≤10150\le L\le R\le 10^{15},0≤ai≤10150\le a_i\le 10^{15}。

子任务编号 特殊限制 分值
11 ∑n≤30\sum n\le 30,R≤80R\le 80 1515
22 ∑n≤100\sum n \le 100,R≤200R \le 200
33 ∑n≤500\sum n\le 500,R−L≤600R-L\le 600 2020
44 存在一个点的度数为 n−1n-1 1515
55 3535