kush_76's blog

By kush_76, history, 4 years ago, In English

Hey everyone.. Actually i've been struggling in this tree dp question 161 Dfor about 2 days now.. I read the tutorial but wasn't able to understand it properly. The Problem goes as follows :

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 that have a distance of exactly k between them. Note that pairs (v, u) and (u, v) are considered to be the same pair.

Input

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.

Example Input :

5 2

1 2

2 3

3 4

2 5

Example Output :

4

Please help me out on this one. Thanks in advance!

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By kush_76, history, 5 years ago, In English

Hello everyone.. This is my first cf blog so please be polite to me.

I have been doing competitive programming for a year but i am not seeing any improvement in me. My performances in contests is very poor and i am not able to solve div2 B or C questions. I am not able to figure out what's going wrong.. Please someone help me figure the way to practice effectively. I know this is a very common issue but still please help..

Full text and comments »

  • Vote: I like it
  • +17
  • Vote: I do not like it