D — считаем две динамики, dp1[v] — минимальное время чтобы обойти все, что нужно в поддереве v, и в конце вернутся в v. dp2[v] — минимальное время чтобы обойти все, что нужно в поддереве v, и закончить где-угодно. Это считали, будто v корень. Но ответ это минимум по всем v, значит нужно просто быстро обновлять эти динамики, когда мы переподвешиваем дерево, для этого нужно хранить два максимума -- понятно какие. Итого сложность O(N).

А можно посмотреть чье-нибудь решение J на джаве? Ниасиливаю запихать.

сможете помочь как оптимально решать B.Battle of Giants

E: пусть n нечетно. Тогда: а) Первый игрок может при любой игре второго собрать все стоящие на 1,3,5,..., n-ом местах элементы; б) а второй игрок всегда может собрать 2,4,...,n-1-ый элементы. Следовательно, ответ при нечетном n есть суммы элементов с нечетных и четных позиций.

Для четного n решаем задачу с помощью очевидной динамики за квадрат и вышеописанного наблюдения для отрезков нечетной длины. С помощью линейного предподсчета частичных сумм можно находить сумму чисел на позициях нужной четности на нужном подотрезке за О(1) => в динамике ответ для четного отрезка найдется из двух ответов для двух нечетных отрезков (берем одно число) за О(1) и ответ для четного отрезка на 2 меньшей длины => имеем О(n)-ое решение.

H: рассмотрим такие вершины многоугольника (назовем из "невыпуклыми"), что из четырех смежных с ней клеточек смежными являются ровно 3. УТВ. 0: из каждой такой вершины можно провести две стенки; УТВ. 1: если стенки разбили фигуру на прямоугольники, то для каждой невыпуклой вершины одна из инцидентных ей стенок обязательно есть; УТВ. 2: и наоборот, если для каждой невыпуклой вершины есть инцидентная ей стенка, то имеющийся набор стенок разбивает фигуру на прямоугольники.

Исходя из этого, имеем решение: 0) находим невыпуклые вершины; 1) строим граф, вершинами которого являются невыпуклые вершины многоугольника; 2) находим минимальное множество ребер, покрывающее все вершины.

2: делается тривиально, ибо граф есть набор цепочек и простых циклов; 0: пусть многоугольник ориентирован по часовой стрелке. Тогда вершина невыпуклая <=> при прохождении через нее мы "поворачиваем налево"; 1 (и самое сложное): сжатие координат + сканлайн + дерево отрезков с присваиванием на отрезке. Делаем 2 раза (вдоль вертикали и вдоль горизонтали). События в сканлайне — вертикальные ребра в 1-ом проходе и горизонтальные во 2-ом.

Итого О(n log n).