This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
import java.util.*;
import java.io.*;
public class burza {
static int[] dp;
static ArrayList<ArrayList<Integer>> arr;
public static void main(String[] args) throws IOException {
BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
StringTokenizer st = new StringTokenizer(f.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
dp = new int[n];
arr = new ArrayList<>();
for (int i = 0; i < n; i++) {
arr.add(new ArrayList<>());
}
for (int i = 0; i < n - 1; i++) {
st = new StringTokenizer(f.readLine());
int x = Integer.parseInt(st.nextToken()) - 1;
int y = Integer.parseInt(st.nextToken()) - 1;
arr.get(x).add(y);
arr.get(y).add(x);
}
out.println(fillDp(0, new boolean[n]) >= k ? "DA" : "NE");
out.close();
f.close();
}
public static int fillDp(int i, boolean[] visited) {
visited[i] = true;
if (dp[i] != 0) return dp[i];
if (arr.get(i).size() == 0) return 0;
else if (arr.get(i).size() == 1 && i != 0) return 0;
ArrayList<Integer> pos = new ArrayList<>();
for (int x : arr.get(i)) {
if (!visited[x])
pos.add(fillDp(x, visited) + 1);
}
Collections.sort(pos);
if (pos.size() == 1) return 0;
return dp[i] = pos.get(pos.size() - 2);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |