Advertisement
vov44k

Untitled

Mar 17th, 2023
559
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.34 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.Scanner;
  3.  
  4. public class Main {
  5.     static ArrayList<Integer>[] graph;
  6.     static int[] d;
  7.     static boolean[] visited;
  8.     static int ans = 0;
  9.  
  10.     static void dfs(int v) {
  11.         visited[v] = true;
  12.         int max1 = -1;
  13.         int max2 = -1;
  14.         for (int i = 0; i < graph[v].size(); i++) {
  15.             int to = graph[v].get(i);
  16.             if (!visited[to]) {
  17.                 dfs(to);
  18.                 if (d[to] >= max1) {
  19.                     int t = max1;
  20.                     max1 = d[to];
  21.                     max2 = t;
  22.                 } else if (d[to] > max2) {
  23.                     max2 = d[to];
  24.                 }
  25.             }
  26.         }
  27.         ans = Math.max(ans, (max1 + max2 + 2));
  28.         d[v] = max1 + 1;
  29.     }
  30.  
  31.     public static void main(String[] args) {
  32.         Scanner s = new Scanner(System.in);
  33.         int n = s.nextInt();
  34.         graph = new ArrayList[n];
  35.         for (int i = 0; i < n; i++) {
  36.             graph[i] = new ArrayList<Integer>();
  37.         }
  38.         d = new int[n];
  39.         visited = new boolean[n];
  40.         for (int i = 0; i < n - 1; i++) {
  41.             int x = s.nextInt() - 1;
  42.             int y = s.nextInt() - 1;
  43.             graph[x].add(y);
  44.             graph[y].add(x);
  45.         }
  46.         dfs(0);
  47.         System.out.println(ans);
  48.     }
  49. }
  50.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement