kush_76's blog

By kush_76, history, 5 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!

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

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you so much man !! Really helped

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice explanation but can you explain this solution too??

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Very well explained......Thankyou

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks , After struggling with other hashing and tougher dp recurrences , This solution made the task very easy

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem is all about rerooting technique. You can see the editorial of problem F of this blog. https://codeforces.net/blog/entry/74714
Now, 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.

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Since the post appeared in recent actions, it's not even necroposting, so I might as well say that this task on steroids can be solved by centroid decomposition + FFT to get a solution for all possible k in O(n log^2)

https://judge.yosupo.jp/problem/frequency_table_of_tree_distance