CF161D Distance in Tree

    • 201通过
    • 579提交
  • 题目来源 CodeForces 161D
  • 评测方式 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类违反进行处理。