-
Notifications
You must be signed in to change notification settings - Fork 0
/
AuthorSol.java
144 lines (129 loc) · 2.8 KB
/
AuthorSol.java
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
import java.util.StringTokenizer;
public class AuthorSol {
static ArrayList<Integer>[] adj;
static int res = 0;
public static void main(String[] args) {
FastScanner fs = new FastScanner();
PrintWriter out = new PrintWriter(System.out);
int T = 1;
T = fs.nextInt();
for (int tc = 1; tc <= T; tc++) {
int n = fs.nextInt(), k = fs.nextInt();
adj = new ArrayList[n];
for (int i = 0; i < n; i++) {
adj[i] = new ArrayList<>();
}
for (int i = 0; i < n - 1; i++) {
int u = fs.nextInt(), v = fs.nextInt();
--u; --v;
adj[u].add(v);
adj[v].add(u);
}
int low = 1, high = n / (k + 1) + 1;
while (high - low > 1) {
int mid = (low + high) / 2;
if (check(mid, k)) {
low = mid;
} else {
high = mid;
}
}
System.out.println(low);
}
out.close();
}
static boolean check(int x, int k) {
res = 0;
int t = dfs(0, 0, x);
return (res > k || (t >= x && res == k));
}
static int dfs(int u, int parent, int x) {
int sz = 1;
for (int v : adj[u]) {
if (v == parent) {
continue;
}
sz += dfs(v, u, x);
}
if (sz >= x && parent != u) {
res++;
sz = 0;
}
return sz;
}
static final Random rnd = new Random();
static void shuffleSort(int[] a) { //change this
int n = a.length;
for (int i = 0; i < n; i++) {
int newInd = rnd.nextInt(n);
int temp = a[newInd]; //change this
a[newInd] = a[i];
a[i] = temp;
}
Arrays.sort(a);
}
static class FastScanner {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer("");
String next() {
while (!st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
int[] readArray(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
long[] readLongArray(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = nextLong();
}
return a;
}
double[] readDoubleArray(int n) {
double[] a = new double[n];
for (int i = 0; i < n; i++) {
a[i] = nextDouble();
}
return a;
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try {
if (st.hasMoreTokens()) {
str = st.nextToken("\n");
} else {
str = br.readLine();
}
} catch(IOException e) {
e.printStackTrace();
}
return str;
}
}
}