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!
dp on trees tutorial
Thank you so much !!
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
Thank you so much man !! Really helped
Nice explanation but can you explain this solution too??
Very well explained......Thankyou
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.
then divide the final answer by 2.
Thanks , After struggling with other hashing and tougher dp recurrences , This solution made the task very easy
This problem is all about rerooting technique. You can see the editorial of problem F of this blog. https://codeforces.me/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.
can u elaborate on rerooting a little bit and how is it applicable here?
I have explained in depth, the rerooting technique in the following videos :
Problem 1 : https://youtu.be/nGhE4Ekmzbc
Problem 2 : https://youtu.be/N7e4CTfimkU
Enjoy watching!
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