### furious's blog

By furious, 10 years ago,

Hey!

Tell me plz how to find the diameter of a tree using DP. Thanks in advance! :)

• +5

 » 10 years ago, # |   0 Use DFS!
•  » » 10 years ago, # ^ |   0 Oh, that's not interesting)
 » 10 years ago, # |   +1 Pick any vertex as source vertex. Find the most distant vertex from the source. Make this vertex new source. Repeat step 2 two times. Distance between the source and the the most distant vertex from the source is diameter.
•  » » 10 years ago, # ^ | ← Rev. 2 →   0 that's not dynamic programming. but thanks, anyways.
•  » » 6 years ago, # ^ |   0 can you explain in step 3 why have you asked to repeat step 2 , two times. once i have the farthest node from root (lets mark it as A)only one more time DFS(A) should yield another node(let say B) that is farthest from A node and the question seem to be solved. Please correct me if i am wrong.
•  » » » 6 years ago, # ^ |   +3 Yes, one time is enough. I guess he had meant that you need to do step 2 two times in total.
 » 10 years ago, # |   +1 Another way. Run DFS from the root. In each subtree, we find the length of the longest path from the root of this subtree to some descendant of it. It is clear, how we can compute the answer for some vertex. We solve the problem for each of its children, and the answer for this vertex is 1+max where max is the longest path from one of the children to some descendant of it.Then the answer to the problem is the maximum value over the , for each vertex and two of its children.
•  » » 10 years ago, # ^ |   0 Thanks for the idea, but I think it won't work at this test, for example1 2 2 3 3 4 3 5 3 6Because 1 has only left subtree
•  » » » 10 years ago, # ^ | ← Rev. 2 →   0 Well, of course, we need to consider also , for the root, if it has only one child. Thanks for the note.
•  » » » » 10 years ago, # ^ | ← Rev. 3 →   0 and here comes another question: why do we find the path that covers the root of the subtree. I think that's not true. For example, 1 2 2 3 3 4 2 5 5 6 6 7 1 8 Your answer is 7, but it should be 5. Thanks for the reply.
•  » » » » » 10 years ago, # ^ |   0 Wait, why 7?
•  » » » » » » 10 years ago, # ^ |   0 cause dfs(2) = 5, dfs(8)=0 5+1+0+1=7, if I understand you correctly)
•  » » » » » » » 10 years ago, # ^ |   0 No, no, dfs doesn't return that value. Think of it in this way: first we calculate only max values for each of the vertices, and only then we try to find a pair of two children of some vertex which maximizes the 2 + max1 + max2. So, for example, in this case: dfs(3) = 1 (path 3-4) dfs(5) = 2 (path 5-6-7) dfs(2) = 3 (path 2-5-6-7) dfs(1) = 4 (path 1-2-5-6-7)
•  » » » » » » » » 10 years ago, # ^ | ← Rev. 2 →   0 why dfs(1) = 4? it should be 5 And dfs(2) should return 5 (4-3-2-5-6-7), shouldn't it?
•  » » » » » » » » » 10 years ago, # ^ |   0 I counted the number of edges, not the number of vertices on the path.
•  » » » » » » » » » 10 years ago, # ^ |   +3 Yes, but 4-3-2-5-6-7 is the longest path and amount of edges is 5
•  » » » » » » » » » 10 years ago, # ^ |   0 ############################################Yes, and when we look at vertex 2 (after dfs), we see that child 3 has max1 = 1 edges, and child 5 has max2 = 2 edges. So we can relax our answer to 2+1+2=5 edges.
•  » » » » » » » » » 10 years ago, # ^ |   +3 I finally understood. Thank you!
•  » » » » » » » » » 10 years ago, # ^ |   +3 Great! And I think it can be counted as DP. (:
•  » » » » » » » » » 6 years ago, # ^ |   0 Nice Explanation
•  » » » » » » » » » 2 years ago, # ^ |   0 sorry to disturb you after 7 years, can you tell me how to find end nodes of diameter?
•  » » » » » » » » » 2 years ago, # ^ |   0 Check the editorial of problem F from Codefoces #615(Div.3)
 » 17 months ago, # | ← Rev. 5 →   0 store the best and second best depths of children of every node in dp[node].Here's the code for storing all values int ans = 0; void dfs(int a, int p, vector>& adj, vector& dp){ pii& pa = dp[a]; for(auto x: adj[a]){ if(x != p){ dfs(x, a, adj, dp); if(dp[x].X + 1 >= pa.X){ pa.Y = pa.X; pa.X = dp[x].X + 1; } else if(dp[x].X + 1 > pa.Y){ pa.Y = dp[x].X + 1; } } } ans = max(ans, pa.X + pa.Y); }