hihoCoder 1050 트 리 중 가장 긴 길, 가장 상세 한 문제 풀이 보고서

제목: 나무 중 가장 긴 길
문제 풀이 방향: 모든 점 을 전환점 t 로 삼 아 t 를 뿌리 노드 로 하 는 서브 트 리 중의 '최 장 로' 와 '최 장 로' 와 겹 치지 않 는 '차장 로' 를 구하 고 이 두 길의 길이 의 합 으로 답 을 업데이트 한다. 최종 답 은 바로 이 나무의 최 장 길이 이다.각 노드 에 유사 한 후 순위 로 차례대로 접근 하고 아래 에서 위로 각 노드 의 first 값 과 second 값 을 차례대로 계산 하면 O (N) 의 시간 복잡 도로 이 문 제 를 해결 할 수 있다.
구체 적 인 알고리즘 (자바 버 전, 직접 AC 가능)

  1 import java.util.*;
  2 
  3 public class Main {
  4 
  5     public class Node {
  6         public Node parent;//   
  7         public List<Node> children;//   
  8         public int first;  //   
  9         public int second;//   
 10         public int val;
 11 
 12         public Node(int val, Node parent) {
 13             this.val = val;
 14             this.first = 0;
 15             this.second = 0;
 16             this.parent = parent;
 17             this.children = new ArrayList<Node>();
 18         }
 19 
 20         //     first second
 21         public void update() {
 22             if (this.children.size() == 0) {//   
 23                 this.first = this.second = 0;
 24             } else if (this.children.size() == 1) {//       
 25                 this.first = this.children.get(0).first + 1;
 26                 this.second = 0;
 27             } else {//    2    
 28                 int[] array = new int[this.children.size()];
 29                 for (int i = 0; i < this.children.size(); i++) {
 30                     array[i] = this.children.get(i).first;
 31                 }
 32                 Arrays.sort(array);
 33                 this.first = array[array.length - 1] + 1;
 34                 this.second = array[array.length - 2] + 1;
 35             }
 36         }
 37 
 38         //       first second（          ）
 39         public void updateAll() {
 40             for (Node child : this.children) {
 41                 child.updateAll();
 42             }
 43             this.update();
 44         }
 45     }
 46 
 47     public int n;
 48     public int index;
 49     public int max;
 50     public Node[] nodeMap;
 51 
 52     public Main(Scanner scanner, int n) {
 53         this.n = n;
 54         this.nodeMap = new Node[this.n + 1];
 55         for (int i = 0; i < n - 1; i++) {
 56             this.create(scanner.nextInt(), scanner.nextInt());
 57         }
 58         this.index = 1;
 59         this.nodeMap[this.index].updateAll();//       
 60         this.max = this.nodeMap[this.index].first
 61                 + this.nodeMap[this.index].second;
 62         this.index++;
 63     }
 64 
 65     //   
 66     private void create(int from, int to) {
 67         Node parent = this.nodeMap[from];
 68         Node child = this.nodeMap[to];
 69         if (parent == null) {
 70             parent = new Node(from, null);
 71             this.nodeMap[from] = parent;
 72         }
 73         if (child == null) {
 74             child = new Node(to, parent);
 75             this.nodeMap[to] = child;
 76         }
 77         child.parent = parent;
 78         parent.children.add(child);
 79     }
 80 
 81     //    i         
 82     private void setRoot(int i) {
 83         Node cur = this.nodeMap[i];
 84         Node parent = cur.parent;
 85         if (parent != null) {//       
 86             parent.children.remove(cur);//          
 87             this.setRoot(parent.val);//       
 88             cur.children.add(parent);//         
 89             parent.parent = cur;
 90         }
 91         cur.update();//      
 92     }
 93 
 94     public void solve() {
 95         while (this.index <= this.n) {
 96             this.setRoot(this.index);
 97             this.nodeMap[this.index].parent = null;//    parent   null，       
 98             int sum = this.nodeMap[this.index].first
 99                     + this.nodeMap[this.index].second;
100             this.index++;
101             this.max = this.max > sum ? this.max : sum;//  max
102         }
103     }
104 
105     public static void main(String[] args) {
106         Scanner scanner = new Scanner(System.in);
107         int N = scanner.nextInt();
108         Main main = new Main(scanner, N);
109         main.solve();
110         System.out.println(main.max);
111     }
112 
113 }