1

Тема: Начинающий маг - Codeforces

Здравствуйте, у меня возникла.. заминка с решением задачи.

Пятая Липецкая командная олимпиада школьников по программированию. Финал. 8-11 классы. Задача C - Начинающий маг
https://codeforces.com/gym/102599/problem/C

Если вкратце её пересказать, нам дано дерево и некое значение "К". Нужно найти любые 2 вершины (V1, V2) этого дерева, таких чтобы:
1) расстояния от корня у них совпадали H(V1) = H(V2);
2) "К" должно быть большим либо равным количеству вершин в пути от корня: U = H(V1) + H(V2) - H( LCA(V1,V2) ), U<=K
3) это количество должно быть максимальным MAX(U)

Всё бы хорошо, но количество вершин в дереве 2*10^5, если в лоб перебирать все возможные сочетания вершин, получим O(N^2), который даст TL (time limit) даже если LCA будем за O(1) считать. В качестве контрпримеров к большинству "оптимизаций" удобно рассматривать: одноуровневое дерево (все вершины у корня), бинарное дерево, и две ветви на некоем отдалении от корня.

Если H, LCA уметь считать за O(1), тогда и характеристику U мы можем узнать за константное время. Но как узнать максимально возможное U для всех пар вершин дерева находящихся на одном уровне меньше чем за O(N^2) ?

2

Re: Начинающий маг - Codeforces

Не правильно ли будет сделать обход в глубину, возвращающий самую глубокую вершину в поддереве, и брать для каждой вершины два самых больших результата среди всех её сыновей?

3 Отредактировано outoftime (2020-10-08 22:36:13)

Re: Начинающий маг - Codeforces

Если вы хотите решить сами - не читайте дальше, подсказки выше, вполне, достаточно.

Для каждой вершины при обходе в глубину надо найти максимальную U среди всех поддеревьев (т.е. LCA находится в поддереве) и случая когда LCA будет текущая вершина.

Для случая когда LCA - текущая вершина, возвращать самую глубокую вершину поддерева - достаточно.
Для случая когда LCA в поддереве, нам нужно знать минимум пару вершин и высоту с учётом ограничения по k.

Получается надо возвращать максимально глубокую и ответ для поддерева (v1, v2, h) с учётом ограничения по K.

Самым сложным было выделить 2 случая: когда LCA в поддереве и надо просто выбрать лучший результат и когда LCA - текущая вершина и надо найти наибольшую возможную высоту соответствующую ограничению по k.

В конечном итоге, вышло:

DFS(v, h) -> (h_max, v_max), (v1, v2, h_norm)
, где (h_max, v_max) - пара высоты и индекса вершины, для лексикографического сравнения и выделения 2х максимальных;
v1, v2 - пара максимальных вершин, которые нужно привести к высоте h_norm при выводе ответа;
v - текущая вершина;
h - текущая высота;

По-идее, достаточно просто v1, v2, h_norm, но в моей реализации было удобнее вернуть ещё 2 доп. значения. Да и я возвращаю, по-сути, 2 ответа. Первый использую для поиска ответа на задачу, а 2й для вывода результата.