diameter of a tree - Codeforces

furious's blog

diameter of a tree

By furious, 11 years ago, In Russian

Hey!

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

diameter, tree

furious
11 years ago
23

Comments (22)

Show archived | Write comment?

scorpion

11 years ago, # |

Use DFS!

→ Reply

furious

11 years ago, # ^ |

Oh, that's not interesting)

→ Reply

Fefer_Ivan

11 years ago, # |

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.

→ Reply

furious

11 years ago, # ^ |

← Rev. 2 →

that's not dynamic programming. but thanks, anyways.

→ Reply

da.2396

8 years ago, # ^ |

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.

→ Reply

UnknownNooby

8 years ago, # ^ |

Yes, one time is enough.

I guess he had meant that you need to do step 2 two times in total.

→ Reply

gen

11 years ago, # |

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 $\text{[math]}$ , for each vertex and two of its children.

→ Reply

furious

11 years ago, # ^ |

Thanks for the idea, but I think it won't work at this test, for example

1 2 2 3 3 4 3 5 3 6

Because 1 has only left subtree

→ Reply

gen

11 years ago, # ^ |

← Rev. 2 →

Well, of course, we need to consider also $\text{[math]}$ , for the root, if it has only one child. Thanks for the note.

→ Reply

furious

11 years ago, # ^ |

← Rev. 3 →

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.

→ Reply

gen

11 years ago, # ^ |

Wait, why 7?

→ Reply

furious

11 years ago, # ^ |

cause dfs(2) = 5, dfs(8)=0 5+1+0+1=7, if I understand you correctly)

→ Reply

gen

11 years ago, # ^ |

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 + max₁ + max₂. 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)

→ Reply

furious

11 years ago, # ^ |

← Rev. 2 →

why dfs(1) = 4? it should be 5 And dfs(2) should return 5 (4-3-2-5-6-7), shouldn't it?

→ Reply

gen

11 years ago, # ^ |

I counted the number of edges, not the number of vertices on the path.

→ Reply

furious

11 years ago, # ^ |

Yes, but 4-3-2-5-6-7 is the longest path and amount of edges is 5

→ Reply

gen

11 years ago, # ^ |

############################################

Yes, and when we look at vertex 2 (after dfs), we see that child 3 has max₁ = 1 edges, and child 5 has max₂ = 2 edges. So we can relax our answer to 2+1+2=5 edges.

→ Reply

furious

11 years ago, # ^ |

I finally understood. Thank you!

→ Reply

gen

11 years ago, # ^ |

Great! And I think it can be counted as DP. (:

→ Reply

sunnycarlos

4 years ago, # ^ |

sorry to disturb you after 7 years, can you tell me how to find end nodes of diameter?

→ Reply

BOGDAN_

4 years ago, # ^ |

Check the editorial of problem F from Codefoces #615(Div.3)

→ Reply

steadyEffort

3 years ago, # |

← Rev. 5 →

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<vector<int>>& adj, vector<pii>& 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);
}

→ Reply