Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### kush_76's blog

By kush_76, history, 17 months ago,

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

• 0

 » 17 months ago, # |   0
•  » » 17 months ago, # ^ |   0 Thank you so much !!
 » 17 months ago, # |   +3 1st of all let us root the tree at any arbitrary node(say node 1). Let's define dp1(u,x) = number of nodes that have a distance x from u. dp2(u,x) = number of nodes that have a distance x from u and lie in the subtree rooted at node u.Now our ans is simply going to be sum of dp1(i, k) where i = 1 to N. Calculating dp2(u,x) should be trivial.dp2(u,x) = summation dp2(c, x-1) where c is a child of u. dp2(u,0) = 1.Now comparatively harder part is calculating dp1.For the root node : dp1(root, x) = dp2(root, x). Now For node u (u is not the root): dp1(u, x) = dp2(u,x) + {dp1(parent[u], x-1) — dp2(u, x-2)}Explanation : dp1(u, x) is obvious when u = root. dp1(u, x) will be the number of nodes in the tree that are at distance x from u. dp1(u, x) consists of nodes that may be in the subtree rooted at node u or may not be. dp2(u, x) gets us all nodes at dis x from u and in subtree of u. now we now only need to add nodes at distance x but not in subtree of u. we know number of nodes at dis x-1 from parent of u and u is at dis 1 from u. all these nodes need to be counted except for those nodes which are in the subtree rooted at u, so take all these but subtract dp2(u, x-2) as dp1(parent[u], x-1) = sum dp1(c, x-2) over all c.Time complexity : N*K
•  » » 17 months ago, # ^ |   0 Thank you so much man !! Really helped
•  » » 15 months ago, # ^ |   0 Nice explanation but can you explain this solution too??
•  » » 14 months ago, # ^ |   +5 Very well explained......Thankyou
•  » » 14 months ago, # ^ |   0 If every node contains count of nodes at K unit distance then don't you think it includes node twice as we just do summation and we are expecting only a distinct pair.
•  » » » 14 months ago, # ^ |   0 then divide the final answer by 2.
•  » » 12 months ago, # ^ |   0 AC solution based on above idea : https://codeforces.com/contest/161/submission/93595381
•  » » 3 weeks ago, # ^ |   0 Thanks , After struggling with other hashing and tougher dp recurrences , This solution made the task very easy
 » 15 months ago, # |   0 This problem is all about rerooting technique. You can see the editorial of problem F of this blog. https://codeforces.com/blog/entry/74714Now, let's root the tree at 1. Let dp[i][j] = the number of paths of length j in the subtree of vertex i starting from vertex i. Try out yourself the rest. It's just now an exercise on rerooting technique.
•  » » 15 months ago, # ^ |   0 can u elaborate on rerooting a little bit and how is it applicable here?
•  » » » 14 months ago, # ^ | ← Rev. 2 →   0 I have explained in depth, the rerooting technique in the following videos :Problem 1 : https://youtu.be/nGhE4Ekmzbc Problem 2 : https://youtu.be/N7e4CTfimkUEnjoy watching!
•  » » 12 months ago, # ^ |   0 hossainzarif , I can't see how we can solve this problem using rerooting technique. Can you please explain or give a link to your submission ?