Ш
Ну то есть, я не вижу смысла особо подсказывать, когда вы уже сделали 70% умозаключений сами и осталось только сесть и dfs написать
А как востановить ответ ?
Size: a a a
2020 March 08
Ш
DK
А как востановить ответ ?
Так как ответ не превосходит N, то можно просто хранить вектор из индексов ребер
DK
Либо, если не влезет по памяти (может быть дерево в виде списка и тогда памяти N^2), то ссылку, (откуда пришли, какое ребро добавить в ответ)
DK
Можно что-то придумать, так как для каждой вершины мы добавляем не более одного ребра, то это ребро и хранить
KK
так это же максимальное паросочетание
Паросоч на 1е5?
DK
Либо, если не влезет по памяти (может быть дерево в виде списка и тогда памяти N^2), то ссылку, (откуда пришли, какое ребро добавить в ответ)
Можно память подчищать у вершин, к которым больше никогда не обратимся в рекурсии, тогда O(n) памяти под хранение ответа
K
Паросоч на 1е5?
в данном случае оптимизируется, да
KK
Лол, там в комментах пишут, что даже кун заходит
KK
А что за дп? Идем от листа и юз/не юз в каждого ребенка?
AD
из поддерева вернуть 2 числа: если брать текущую вершину и если не брать
SF
A
Интересно, эта задача лежит в NP?
english please
CD
Интересно, эта задача лежит в NP?
Да, по числу строк
A
Интересно, эта задача лежит в NP?
да
SF
И как ее решать за полином на недетерминированной машине Тьюринга?
A
Интересно, эта задача лежит в NP?
но мы можем оптимизировать его с помощью DP
CD
И как ее решать за полином на недетерминированной машине Тьюринга?
Сертификат для "длина кратчайшей не превышает N" имеет полиномиальную длину
KK
Ajay
но мы можем оптимизировать его с помощью DP
Нет
KK
Мы можем саппроксимировать эту штуку через машобуч