[Link] https://AtCoder.jp/contests/typical90/tasks/typical90_c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int n = Integer.parseInt(bf.readLine());
ArrayList<HashSet<Integer>> connection = new ArrayList<HashSet<Integer>>();
for(int i = 0; i < n; i++) {
connection.add(new HashSet<>());
}
Stack<int[]> stack = new Stack<>();
for(int i = 1; i < n; i++) {
st = new StringTokenizer(bf.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
connection.get(a - 1).add(b);
connection.get(b - 1).add(a);
}
int max = 0;
int farthestTown = 0;
int[] temp1 = {1, 0};
stack.push(temp1);
boolean[] visited = new boolean[n + 1];
while(!stack.isEmpty()) {
int[] top = stack.pop();
int town = top[0];
int len = top[1];
if(visited[town]) continue;
visited[town] = true;
if(max < len) {
max = len;
farthestTown = town;
}
for(int e : connection.get(town - 1)) {
if(visited[e]) continue;
int[] temp2 = { e, len + 1};
stack.push(temp2);
}
}
int[] temp3 = { farthestTown, 0};
stack.push(temp3);
visited = new boolean[n + 1];
while(!stack.isEmpty()) {
int[] top = stack.pop();
int town = top[0];
int len = top[1];
if(visited[town]) continue;
visited[town] = true;
for(int e : connection.get(town - 1)) {
if(visited[e]) continue;
if(max < len + 1) max = len + 1;
int[] temp2 = {e, len + 1};
stack.push(temp2);
}
}
System.out.println(max + 1);
}
}