Блог пользователя furious

Автор furious, 13 лет назад, По-русски

Hey!

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

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Use DFS!

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится
  1. Pick any vertex as source vertex.
  2. Find the most distant vertex from the source. Make this vertex new source.
  3. Repeat step 2 two times.
  4. Distance between the source and the the most distant vertex from the source is diameter.
»
13 лет назад, скрыть # |
 
Проголосовать: нравится +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.

»
5 лет назад, скрыть # |
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<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);
}