Вот задача
Мое решение: взять все листья, последовательно удалять их. Если вершина, к которой лист был присоединен сама стала листом, добавить её в очередь к листьям. Поддерживать массив deleted, в котором хранится количество вершин, удаленных перед этой вершиной (но не во всем дереве, а так, что их удаление делает эту вершину листом). Лист добавится в очередь только если количество удаленных листьев кратно k (эти листья изначально могли ими не быть, но если стали - сумма значений из deleted, соответствующая им, тоже кратна k). В deleted найти максимальное значение поделить на k, это ответ.
Решение не проходит 19-й тест (мой ответ 2, нужно 3). В чем может быть проблема?
Код
import java.util.*;
import java.io.*;
public class F {
FastScanner sc;
PrintWriter out;
Map<Integer, Set<Integer>> tr;
Queue<Integer> findLeaves() {
var res = new ArrayDeque<Integer>();
for (Integer v: tr.keySet())
if (tr.get(v).size() == 1)
res.offer(v);
return res;
}
private void solve() {
sc = new FastScanner(System.in);
out = new PrintWriter(System.out);
int t = sc.nextInt();
for (; t > 0; t--) {
int n = sc.nextInt();
int k = sc.nextInt();
tr = new HashMap<>();
for (int i = 1; i <= n; i++)
tr.put(i, new HashSet<>());
for (int i = 0; i < n-1; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
tr.get(x).add(y);
tr.get(y).add(x);
}
Queue<Integer> leaves = findLeaves();
var deleted = new int[n+1];
var buff = new ArrayDeque<Integer>(); //добавляются сначала в буфер, чтобы не было ConcurrentModificationException
while (!leaves.isEmpty()) {
out.println(leaves);
while (!leaves.isEmpty()) {
Integer v = leaves.poll();
if (tr.get(v).isEmpty())
continue;
Integer p = tr.get(v).iterator().next();
tr.get(p).remove(v);
tr.get(v).remove(p);
deleted[p] += deleted[v] + 1;
if (tr.get(p).size() == 1 && deleted[p] % k == 0) {
buff.add(p);
}
}
while (!buff.isEmpty())
leaves.add(buff.poll());
}
out.println("Deleted:");
for (int i = 1; i <= n; i++)
out.print(deleted[i] + " ");
out.print('\n');
int max = 0;
for (int i = 1; i <= n; i++)
max = Math.max(max, deleted[i]);
out.println(max / k);
}
sc.close();
out.close();
}
private static class FastScanner {
BufferedReader br;
StringTokenizer st;
public FastScanner(InputStream inputStream) {
br = new BufferedReader(new InputStreamReader(inputStream));
}
public String next() {
try {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
e.printStackTrace();
}
return st.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
public void close() {
try {
br.close();
} catch (Exception e) {
e.printStackTrace();
}
}
}
public static void main(String[] args) {
try {
new F().solve();
} catch (Exception e) {
e.printStackTrace();
}
}
}
Средний
