CF161D.Distance in Tree
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
A tree is a connected graph that doesn't contain any cycles.
The distance between two vertices of a tree is the length (in edges) of the shortest path between these vertices.
You are given a tree with n vertices and a positive number k . Find the number of distinct pairs of the vertices which have a distance of exactly k between them. Note that pairs ( v , u ) and ( u , v ) are considered to be the same pair.
树是不包含任何循环的连通图。
树的两个顶点之间的距离是这两个顶点之间最短路径的长度(以边为单位)。
给你一棵有 n 个顶点和一个正数 k 的树。请找出顶点之间距离恰好为 k 的不同顶点对的数目。请注意,( v , u )和( u , v )被视为同一对。
输入格式
The first line contains two integers n and k ( 1<=n<=50000 , 1<=k<=500 ) — the number of vertices and the required distance between the vertices.
Next n−1 lines describe the edges as " ai bi " (without the quotes) ( 1<=ai,bi<=n , ai=bi ), where ai and bi are the vertices connected by the i -th edge. All given edges are different.
第一行包含两个整数 n 和 k ( 1 ≤ n ≤ 50000 , 1 ≤ k ≤ 500 )--顶点数和顶点之间的所需距离。
接下来的 n - 1 行将边描述为" ai "。 bi "(不带引号)( 1 ≤ ai, bi ≤ n , ai ≠ bi ),其中 ai 和 bi 是由第 i 条边连接的顶点。所有给定的边都是不同的。
输出格式
Print a single integer — the number of distinct pairs of the tree's vertices which have a distance of exactly k between them.
Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.
打印一个整数 - 树顶点之间距离正好为 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
说明/提示
In the first sample the pairs of vertexes at distance 2 from each other are (1, 3), (1, 5), (3, 5) and (2, 4).
在第一个样本中,相距 2 的顶点对分别是 (1, 3)、(1, 5)、(3, 5) 和 (2, 4)。