首页 > 试题广场 >

Tree Subset Diameter

[编程题]Tree Subset Diameter
You are given an undirected, unweighted tree T on n nodes. We define the distance between two nodes u, v as the number of edges we need to travel from u to v. We define the diameter of a subset of nodes S as the maximum distance between two elements in S. If the size of S is smaller than or equal to 1, we define the diameter as 0.

Find the number of subsets S of nodes in T such that the diameter of S is exactly D.


输入描述:
The first line of input contains a single integer n (2 ≤ n ≤ 100000).

The next n - 1 lines contains two space-separated integers each, ui, vi (1 ≤ ui ≠ vi ≤ n), describing an edge of the tree connecting ui and vi.

The last line contains a single integer D (1 ≤ D ≤ n).

It is guaranteed that the input graph is a tree.


输出描述:
Output a single integer, the number of subsets of nodes with diameter D. Since the answer might be large, output it modulo 109 + 7.
示例1

输入

4
2 3
1 3
3 4
2

输出

8

说明

For the first sample, the subsets are {1, 2}, {1, 4}, {2, 4}, {1, 2, 3}, {1, 3, 4}, {2, 3, 4}, {1, 2, 4}, {1, 2, 3, 4}.
示例2

输入

4
2 3
1 3
3 4
1

输出

3

说明

For the second sample, the subsets are {1, 3}, {2, 3}, {3, 4}.
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

树
难度：
0条回答 2浏览

热门推荐

通过挑战的用户

查看代码

相关试题

Tree Subset Diameter

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号