Максимальное расстояние между двумя узлами в дереве

Question

Я пытаюсь найти максимальное расстояние между двумя узлами в дереве. Вот моя программа:

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.Scanner; 


public class distance { 

    static ArrayList<ArrayList<Integer>> list=new ArrayList<ArrayList<Integer>>(); 
    static ArrayList<Integer> visited=new ArrayList<Integer>(); 
    static ArrayList<Integer> depth=new ArrayList<Integer>(); 
    static ArrayList<Integer> depth1=new ArrayList<Integer>(); 
    static int sum=-1; 
    static boolean[] arr; 
    static int root=0; 


    public static void main(String args[]) 
    { 
     Scanner in=new Scanner(System.in); 
     int n=in.nextInt();  //no of nodes 

     for(int i=0;i<=n;i++) 
     { 
      list.add(new ArrayList<Integer>()); 
     } 
     int a; 
     int b; 
     for(int i=0;i<n-1;i++) //populating the adjacency list 
     { 
      a=in.nextInt(); 
      b=in.nextInt(); 
      list.get(a).add(b); 
      list.get(b).add(a); 
     } 

     arr=new boolean[n+1]; 

     dfs(root); 

     int final_sum=0; 
     Collections.sort(depth1); 
     System.out.println(depth1.get(depth1.size()-1)+depth1.get(depth1.size()-2)); 

     } 
    public static void dfs(int n) 
    { 
     arr[n]=true; 
     visited.add(n); 
     sum=sum+1; 

     if(list.get(n).size()==1) 
     { 
      depth.add(sum); //add the depth to the arraylist when we reach a leaf node.Note the this will not run if the root node has only one child but I've ignored the case. 
     } 
     if(n==root) 
     { 
      for(int j=0;j<list.get(0).size();j++) 
      { 
       dfs(list.get(0).get(j)); //recursion on each child of the root node 
       sum=0; 
       Collections.sort(depth); 
       depth1.add(depth.get(depth.size()-1)); 
       depth.clear(); 
      } 

     } 
     else 
     { 
      for(int l:list.get(n)) 
      if(!arr[l]==true) 
      { 
       dfs(l); 
       sum--; 

      } 
     } 


    } 

} 

Программа, похоже, работает; но не показывает правильный результат для некоторых тестовых случаев. Подход, который я сделал, это:

1. Найти количество детей корневого узла (я всегда принимал корневой узел равным 0).
2. Найти максимальную глубину каждого поддерева (как много поддеревьев, так как есть дети корневого узла).
3. Сохраните максимальную глубину каждого поддерева в ArrayList, отсортируйте его и распечатайте сумму двух последних значений.

Может кто-нибудь указать на ошибку в моей программе?

Answer 1

Ошибка в алгоритме в первую очередь. Вы предполагаете, что максимальное расстояние между двумя узлами всегда содержит корневой узел, хотя это не всегда верно.

Вот пример:

Узлы из самого длинного пути, помечены красным цветом. Самый длинный путь имеет длину 6 и содержит 7 узлов, в то время как ваш алгоритм находит только пути, которые проходят через корень, и поэтому печатает 5 в качестве своего ответа.