BitNeBolt
@BitNeBolt

Почему не проходит решение?

Вот задача

Мое решение: взять все листья, последовательно удалять их. Если вершина, к которой лист был присоединен сама стала листом, добавить её в очередь к листьям. Поддерживать массив 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();
		}
	}
}

  • Вопрос задан
  • 110 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Ваша идея правильная - тут можно жадно удалять по k листьев, пока можно.

Но ваша логика решения мне не понятна. Вам следует в каждой вершине поддерживать счётчик соседей листьев и их список. Далее, имейте очередь вершин с более чем k листьев рядом. Удаляйте k листьев. Если текущая стала листом (нужны счётчики для степени вершин), то добавьте её в список к единственному соседу.

Чтобы не возиться с удалением соседей, помещайте вершины удаленными и при обходе списка соседей удаляйте их
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы