← 返回题目列表

Codeforces · 161/D

D. 树中的距离

中文机器翻译题面 查看原题

树是不包含任何循环的连通图。

树的两个顶点之间的距离是这些顶点之间的最短路径的长度(以边为单位)。

给你一棵有 n 个顶点和正数 k 的树。求它们之间的距离恰好为 k 的不同顶点对的数量。请注意,对 (v, u) 和 (u, v) 被视为同一对。

输入

第一行包含两个整数 n 和 k (1 ≤ n ≤ 50000, 1 ≤ k ≤ 500) — 顶点数量和顶点之间所需的距离。

接下来的 n - 1 行将边描述为“ai bi”(不带引号)(1 ≤ ai,bi ≤ n,ai ≠ bi),其中 ai 和 bi 是由第 i 条边连接的顶点。所有给定的边都是不同的。

输出

打印一个整数 — 树顶点之间的距离恰好为 k 的不同对的数量。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

5 2
1 2
2 3
3 4
2 5

输出 #1

4

输入 #2

5 3
1 2
2 3
3 4
4 5

输出 #2

2

注意

在第一个样本中,彼此距离为 2 的顶点对为 (1, 3)、(1, 5)、(3, 5) 和 (2, 4)。