# CF161D Distance in Tree

• 201通过
• 579提交
• 题目来源
• 评测方式 RemoteJudge
• 标签 分治 概率论,统计 点分治
• 难度 省选/NOI-
• 时空限制 3000ms / 512MB
• 提示：收藏到任务计划后，可在首页查看。

## 题目大意

输入点数为$N$一棵树

求树上长度恰好为$K$的路径个数

## 输入格式

第一行两个数字$N,K$,如题意

接下来的$N-1$行中,每行两个整数$u,v$表示一条树边$(u,v)$

## 输出格式

一个整数$ans$,如题意

在$Codeforces$上提交时记得用$\%I64d$哦.QwQ

## 数据范围

$1 \leq n \leq 50000$

$1 \leq k \leq 500$

感谢@Zhang_RQ 提供的翻译

## 题目描述

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.

## 输入输出格式

输入格式：

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 " $a_{i}$ $b_{i}$ " (without the quotes) ( $1<=a_{i},b_{i}<=n$ , $a_{i}≠b_{i}$ ), where $a_{i}$ and $b_{i}$ are the vertices connected by the $i$ -th edge. All given edges are different.

输出格式：

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.

## 输入输出样例

输入样例#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).

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。