이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import java.io.*;
import java.util.*;
public class net {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
for(int i = 0; i < n; i++) graph.add(new ArrayList<Integer>());
for(int i = 1; i < n; i++) {
int v1 = s.nextInt() - 1;
int v2 = s.nextInt() - 1;
graph.get(v1).add(v2);
graph.get(v2).add(v1);
}
int[] dist = new int[n];
Queue<Integer> q = new LinkedList<Integer>();
Arrays.fill(dist, -1);
q.add(0);
dist[0] = 0;
while(!q.isEmpty()) {
int node = q.poll();
for(int node2: graph.get(node)) {
if(dist[node2] == -1) {
dist[node2] = dist[node] + 1;
q.add(node2);
}
}
}
/*for(int i = 0; i < n; i++) {
System.out.println(dist[i]);
}*/
boolean found = true;
ArrayList<Integer> ans = new ArrayList<Integer>();
ans.add(1);
for(int i = 1; i < n; i++) {
if(graph.get(i).size() == 1) {
ans.add(i+1);
}
}
Collections.sort(ans, (a, b) -> -1*(dist[a-1] - dist[b-1]));
//System.out.println(ans);
System.out.println((int) ans.size()/2);
for(int i = 0; i < ans.size()/2; i += 1) {
System.out.println(ans.get(i) + " " + ans.get(ans.size() - i - 1));
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |