Why doesn't the solution pass?

Question

Algorithms

Here is the problem

. My solution: take all the leaves, remove them one by one. If the vertex to which the leaf was attached has itself become a leaf, add it to the leaves queue. Maintain the array deleted, which stores the number of vertices deleted before this vertex (but not in the entire tree, but in such a way that deleting them makes this vertex a leaf). The leaf will be added to the queue only if the number of deleted leaves is a multiple of k (these leaves might not have been deleted initially, but if they did, the sum of values ​​from deleted corresponding to them is also a multiple of k). In deleted, find the maximum value divided by k, this is the answer.

The solution fails the 19th test (my answer is 2, I need 3). What could be the problem?

The code

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();
    }
  }
}

Answer 1

Your idea is correct - here you can greedily delete k leaves while you can.
But your logic is not clear to me. You should maintain a count of leaf neighbors and a list of them at each vertex. Next, have a queue of vertices with more than k leaves side by side. Remove k leaves. If the current one has become a leaf (need counters for the degree of vertices), then add it to the list to the only neighbor.
To avoid the hassle of deleting neighbors, put vertices as remote and delete them when iterating through the list of neighbors