Минимальное количество ребер для формирования пути длиной L

Рассмотрим следующий алгоритм:

# Walk the tree in every node from Root node *Recursively (parent-weight=0):
  1 Sort the edges by Weight Descending
  2 Iterate the sorted edges in the node.
    2.1 Calculate the branch-weight: node parent-weight + edge weight
    2.2 IF branch-weight = L THEN Bingo! :)
        ELSE if branch-weight > L THEN Skip edge
        ELSE Walk the egde's end node *Recursively (parent-weight = branch-weight).

Я считаю, что это вполне оптимальный алгоритм.

Есть два основных способа решения этой проблемы; Я опишу более простой метод.

Для начала произвольным образом укорените дерево (вершина 0, как правило, является хорошим выбором, поскольку она всегда существует). Обозначим через dist[x] сумму весов ребер на пути от корня до x, а через depth[x] обозначим количество ребер на этом пути. Для любых двух различных узлов u и v между ними существует один уникальный простой путь, который идет от u к наименьшему общему предку (LCA) двух узлов, а затем к v. Мы можем выразить общий вес на этом пути как dist[u] + dist[v] - 2 * dist[LCA(u, v)], поскольку ребра от корня до LCA учитываются как в dist[u], так и в dist[v]. Аналогично, количество ребер на пути равно depth[u] + depth[v] - 2 * depth[LCA(u, v)].

Далее давайте рассмотрим каждый узел n как возможный LCA на пути между двумя узлами веса L. В этом случае оба этих узла должны находиться в поддереве n (включая его самого). Чтобы вычислить оптимальный ответ в каждом узле, мы будем хранить карту для каждого узла, которая сопоставляет каждому возможному dist[x] минимальное depth[x], которое может достичь этого расстояния для любого x в поддереве n.

Чтобы обработать узел n, мы перебираем каждый дочерний узел c и сначала вычисляем для него эту карту, а затем объединяем этот результат в карту текущего узла в два этапа. Для каждой пары ключ-значение (d, e) в дочернем поддереве мы проверяем карту текущего узла n на наличие ключа k, который удовлетворяет k + d - 2 * dist[n] = L. Если он существует, мы нашли путь веса L. Теперь мы можем обновить наш ответ минимумом текущего ответа и суммой количества ребер для двух частей этого пути. После выполнения всех необходимых обновлений ответа с поддеревом c мы обновляем карту для узла n картой для c, сохраняя минимальное количество ребер для всех замеченных на данный момент расстояний (чтобы убедиться, что мы можем найти оптимальные пути из карты при рассмотрении последующих поддеревьев).

Чтобы эффективно обновлять эти карты, мы будем выбирать всегда обновлять карту с большим количеством ключей, используя карту с меньшим количеством ключей. В худшем случае все узлы имеют разные расстояния от корня. Всякий раз, когда расстояние до определенного узла добавляется от одной карты к другой, результирующая карта должна быть как минимум в два раза больше размера старой карты. Размер любой карты не может превышать N ключей, поэтому каждый элемент можно добавить не более чем на log N карты. Каждый узел вносит свой вклад в обновления log N, поэтому временная и пространственная сложность O(N log N) являются одновременно dist[x].

public static int solve(List<List<Edge>> T, long L) {
    var minEdgesForDist = Stream.<Map<Long, Integer>>generate(HashMap::new).limit(T.size()).collect(Collectors.toCollection(ArrayList::new));
    return new Object() { 
        // creating new object to define methods inside the context of the solve method
        int dfs(int node, int par, int depth, long dist) {
            minEdgesForDist.get(node).put(dist, depth); // for node itself
            int ret = Integer.MAX_VALUE;
            for (var edge : T.get(node))
                if (edge.toVertex != par) {
                    ret = Math.min(ret, dfs(edge.toVertex, node, depth + 1, dist + edge.weight));
                    if (minEdgesForDist.get(edge.toVertex).size() > minEdgesForDist.get(node).size())
                        Collections.swap(minEdgesForDist, edge.toVertex, node); // important!
                    for (var entry : minEdgesForDist.get(edge.toVertex).entrySet()) {
                        var other = minEdgesForDist.get(node).get(L + 2 * dist - entry.getKey());
                        if (other != null)
                            ret = Math.min(ret, entry.getValue() + other - 2 * depth);
                    }
                    for (var entry : minEdgesForDist.get(edge.toVertex).entrySet())
                        minEdgesForDist.get(node).merge(entry.getKey(), entry.getValue(), Math::min);
                }
            return ret;
        }
        
        int getAnswer() {
            int ret = dfs(0, 0, 0, 0);
            return ret != Integer.MAX_VALUE ? ret : -1;
        }
    }.getAnswer();
}