题目名称	2801. 树集
输入输出	`treeset.in/out`
难度等级	★★★
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	TARDIS 于2017-09-11加入
开放分组	全部用户
提交状态
分类标签	动态规划
	分享题解

通过：25，提交：49，通过率：51.02%
雾茗	100	0.001 s	0.05 MiB	C++
LGLJ	100	0.002 s	0.64 MiB	C++
雾茗	100	0.003 s	0.14 MiB	C++
LGLJ	100	0.003 s	1.29 MiB	C++
jekyll	100	0.009 s	0.11 MiB	C++
jekyll	100	0.017 s	0.15 MiB	C++
swttc	100	0.023 s	0.45 MiB	C++
WHZ0325	100	0.028 s	0.34 MiB	C++
liuyu	100	0.029 s	0.37 MiB	C++
Dedsec	100	0.030 s	0.40 MiB	C++

关于树集的近10条评论(全部评论)
抱歉我拉低了通过率。。。 Dedsec 2017-11-02 08:41 2楼
真的是呵呵呵 Arrow 2017-09-27 21:32 1楼

2801. 树集

★★★ 输入文件：treeset.in 输出文件：treeset.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

给出一棵N个节点的树，每个节点上都附有一个权值ai。现在Ann想从中选出若干个节点，满足以下条件：

1. 至少选出一个节点

2. 节点之间是连通的

3. 设节点中权值最大的为ap，最小的为aq，则需要满足ap-aq不大于某个定值D。

XLM想知道有多少种选择的方式？结果对1,000,000,007取模即可。

【输入格式】

第一行包含两个整数D, N，分别代表定值D与节点总数N。

第二行包含N个整数ai，分别代表每个点的权值。

接下来N-1行，每行包含两个数u, v，代表树中节点u与节点v是相连的。>aq，则需要满足ap-aq不大于某个定值D。

Ann想知道有多少种选择的方式？结果对1,000,000,007取模即可。

【输出格式】

一个整数，代表方案数模1,000,000,007的结果。

【样例输入】

【样例输出】

【提示】

8个选择方式为：{1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {3, 4}, {1, 3, 4}。

对于30% 的数据，1<=n<=10;

对于另外的30% 的数据，d=2000.

对于100% 的数据，0<=d<=2000, 1<=n<=2000, 1<=ai<=2000.

【来源】

QBXT