IZ
И вебреха
Size: a a a
2020 March 13
IZ
IZ
Бывалые олимпиадники
IZ
да вроде задача сложной быть не должна
VM
ну пусть есть дерево, посчитаем mini[v] - количество вершин в минимальной компоненте связности, тогда ответ это n - mini[v] для каждой вершины v, разве нет?
VM
ну если наша вершина, это не лист, видимо
MB
ну пусть есть дерево, посчитаем mini[v] - количество вершин в минимальной компоненте связности, тогда ответ это n - mini[v] для каждой вершины v, разве нет?
только не минимальной а максимальной
VM
иначе n
MB
ну если наша вершина, это не лист, видимо
У листа максимальное поддерево как раз N-1, все ок работает)
VM
мне все-таки кажется, что минимум надо брать
VM
а, или максимум все-таки
VM
ну короче одно из двух
VM
все-таки минимум
A
короче решение существует, доказываем неконструктивно
VM
если есть два сына c размерами 1 и inf, то ответ inf + 1 = n - 1 + 1 (т.к. n = inf + 2)
MB
если есть два сына c размерами 1 и inf, то ответ inf + 1 = n - 1 + 1 (т.к. n = inf + 2)
значит ответ - это максимальное плюс один.
Оценка:
Если мы выберем все это поддерево, то получили контрпример на все меньшие ответы.
Пример:
А то, что наш достижим, понятно: эти вершины попали хотя бы в два различных поддерева. А значит их LCA будет корень.
Оценка:
Если мы выберем все это поддерево, то получили контрпример на все меньшие ответы.
Пример:
А то, что наш достижим, понятно: эти вершины попали хотя бы в два различных поддерева. А значит их LCA будет корень.
VM
ой, я вообще не то сделал, сорян
2020 March 15
SB
подскажите плиз, как называется алгоритм который позволяет слить два сортированных файла(или два списка или еще чего угодно) в один сортированный
То есть всегда выбирается наименьший из двух.
То есть всегда выбирается наименьший из двух.
SB
Хотелось бы погуглить имплементацию, потому что у меня всегда какие-то неточности при обработке граничных ситуаций
v
подскажите плиз, как называется алгоритм который позволяет слить два сортированных файла(или два списка или еще чего угодно) в один сортированный
То есть всегда выбирается наименьший из двух.
То есть всегда выбирается наименьший из двух.