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

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