import java.io.*;
import java.util.*;
public class burza {
Map<Integer, List<Integer>> edges = new HashMap<>();
List<Integer> values = new ArrayList<>();
int n;
int k;
int[] left;
int[] right;
int[] depth;
int i = 0;
public static void main(String[] args) throws IOException {
burza b = new burza();
b.solve();
}
public void solve() throws IOException {
BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(f.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
if (k * k + 1 >= n) {
System.out.println("DA");
return;
}
left = new int[n + 1];
right = new int[n + 1];
depth = new int[n + 1];
depth[0] = -1;
List<Integer> temp = new ArrayList<>();
temp.add(1);
edges.put(0, temp);
for (int i = 0; i < n; i++) {
edges.put(i, new ArrayList<>());
}
for (int i = 0; i < n - 1; i++) {
st = new StringTokenizer(f.readLine());
int a = Integer.parseInt(st.nextToken()) - 1;
int b = Integer.parseInt(st.nextToken()) - 1;
edges.get(a).add(b);
edges.get(b).add(a);
}
dfs(0, -1);
/*
* for (int i = 0; i < values.size(); i++) { System.out.println(values.get(i));
* }
*/
boolean[][] dp = new boolean[n][(1 << k)]; // calculates whether the first j leaves of the depth j can be covered by
// the nodes of depth in mask
boolean[][] state = new boolean[(1 << k)][2];
values.remove(values.size() - 1);
for (int t : values) {
for (int j = 0; j < (1 << k); j++) {
// System.out.println(dp.length + " " + left[t] + " " + dp[2].length);
// if (left[t] > 0 && dp[left[t] - 1][j] && (j & (1 << depth[t])) == 0) { //
if (left[t] > 0 && dp[left[t] - 1][j] && (j & (1 << depth[t])) == 0) { //
// essentially the leaves before this and then whether this counts
state[j ^ (1 << depth[t])][1] = true;
}
if (depth[t] < k && state[j][0])
state[j][1] = true;
}
if (left[t] == 0) {
state[1 << depth[t]][1] = true;
}
for (int j = 0; j < state.length; j++) {
state[j][0] = state[j][1];
}
for (int i = 0; i < dp[0].length; i++) {
dp[right[t]][i] = state[i][0];
}
}
for (i = 0; i < dp.length; i++) {
for (int j = 0; j < dp[0].length; j++) {
if(dp[i][j]) {
System.out.println("DA");
return;
}
}
}
System.out.println("NE");
}
private void dfs(int cur, int prev) {
left[cur] = i;
if (depth[cur] < k - 1) {
for (int m : edges.get(cur)) {
if (m != prev) {
depth[m] = depth[cur] + 1;
dfs(m, cur);
}
}
}
i++;
right[cur] = i;
values.add(cur);
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
298 ms |
18940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
960 ms |
80820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1002 ms |
81192 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
426 ms |
26224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
998 ms |
81140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
944 ms |
81072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1014 ms |
81200 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
354 ms |
26148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
295 ms |
18296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
551 ms |
43608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
