Problem 3067 --Dense Subgraph

3067: Dense Subgraph

上一题 正确率: $100.00\%$ 下一题
"
Time Limit $6$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $1$ 正确数量 $1$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

You have a tree on n vertices, and each vertex has a weight av and a degree at most 5.
Let's call the density of a subset of vertices S value ∑v∈Sav|S|, and call the beauty of the tree with some vertices turned off the maximum value of the density of a subset of at least two turned on vertices with connected induced subgraph, or 0 if no such subset exists.
Now you need to calculate the number of ways to choose such a set of turned off vertices among 2n ways that the beauty of the tree is no larger than x, modulo 1000000007.

Input

The input contains several test cases, and the first line contains a single integer T (1≤T≤30), the number of test cases.

The first line of each test case contains two integers n (2≤n≤35000) and x (0≤x≤35000), the number of vertices of a tree and the constraint on the beauty.

The next line contains n integers a1,a2,…,an (0≤ai≤35000), the weights of the tree vertices.

Each of the next n−1 lines contains two integers u and v (1≤u,v≤n), describing an edge connecting vertices u and v in the tree. 

It is guaranteed that each vertex of a tree has a degree at most 5.

Output

For each test case, output a line containing a single integer, indicating the number of ways to choose such a set of turned off vertices among 2n ways that the beauty of the tree is no larger than x, modulo 1000000007.

Sample Input复制

2
5 0
1 1 1 1 1
1 2
2 3
3 4
4 5
3 2
2 1 3
1 2
1 3

Sample Output复制

13
6

推荐代码 查看3067 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$916 $ms] 淡意的温柔 588050 2020-05-27 09:37:44
内存最少[$0 $KB] 淡意的温柔 588050 2020-05-27 09:37:44
第一AC 淡意的温柔 588050 2020-05-27 09:37:44
第一挑战 淡意的温柔 588050 2020-05-27 09:37:44

赛题来源/所属竞赛 2019 Multi-University Training Contest 10 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛