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 ArrayList<Integer>[] adj, kNodes;
static int[][] inv;
static int ctr = 0;
static int N, K;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
adj = new ArrayList[N];
kNodes = new ArrayList[K+1];
inv = new int[N][2];
for(int i = 0; i < N; i++) adj[i] = new ArrayList<>();
for(int i = 0; i <= K; i++) kNodes[i] = new ArrayList<>();
for(int i = 0; i < N-1; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken())-1, B = Integer.parseInt(st.nextToken())-1;
adj[A].add(B);
adj[B].add(A);
}
if(K*K >= N) System.out.println("DA");
else {
dfs(0, 0, -1);
int[] dp = new int[1<<K]; // treat depth 1 as depth 0
dp[0] = -1;
for(int mask = 1; mask < (1 << K); mask++) {
// System.out.println("mask: " + Integer.toBinaryString(mask));
for(int d = 0; d < K; d++) {
if((mask & (1 << d)) == 0) continue;
int prev = dp[mask - (1<<d)];
for(int node : kNodes[d+1]) {
// System.out.println("node: " + node + " bounds: " + inv[node][0] + " " + inv[node][1]);
if(inv[node][0] <= prev+1)
dp[mask] = Math.max(dp[mask], inv[node][1]);
}
}
// System.out.println("dp: " + dp[mask]);
}
// System.out.println("ctr: " + ctr);
if(dp[(1<<K)-1] == ctr-1) System.out.println("DA");
else System.out.println("NE");
}
br.close();
}
public static void dfs(int idx, int depth, int par) {
inv[idx][0] = Integer.MAX_VALUE;
inv[idx][1] = Integer.MIN_VALUE;
if(depth > K) return;
if(depth == K) inv[idx][0] = inv[idx][1] = ctr++;
kNodes[depth].add(idx);
for(int to : adj[idx]) {
if(to == par) continue;
dfs(to, depth+1, idx);
inv[idx][0] = Math.min(inv[idx][0], inv[to][0]);
inv[idx][1] = Math.max(inv[idx][1], inv[to][1]);
}
}
}
Compilation message (stderr)
Note: burza.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
# | 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... |