Минимальное расстояние в графе

Решение, которое работает линейно от числа вершин в графе.

vector< vector<int> > G;
vector<char> isP;
int K;
int dfs2(int v, int p, int l){
    int res = 0;
    for (auto next : G[v])
        if (next !=p)
            res+=dfs2(next,v, l+1);
    if (isP[v])
        res+=l;
    return res;
}

int dfs(int v, int p){
    int res = isP[v];
    for (auto next : G[v])
        if (next !=p)
            res+=dfs(next,v);
    if (res > K/2){
        cout << dfs2(v,-1,0)<<" "<<v<<endl;
        exit(0);
    }
    return res;
}

Запускаемый пример https://ideone.com/eIbkNs

Мы находим первую вершину, в поддереве которой не меньше половины всех отмеченных вершин. И от неё уже считаем расстояния.

Почему это оптимальная вершина. Давайте возьмём любую вершину (X), вычислим от неё все сумму расстояний. Если в каком-то её потомке больше половины вершин, то переместив X в эту вершину, мы уменьшим сумму. Т.к. больше половины путей станут на 1 короче, а меньше половины на 1 длиннее. Повторив это пока возможно, мы получим вершину, в поддереве которой не меньше половины всех отмеченных, но для каждого потомка это не выполняется. Почему минимум расстояний не зависит от выбора исходной вершины X - доказывается аналогично.

Доказательство использует ацикличность графа (упражнение - где именно). Напомню, что связный граф с N-1 ребром и N вершинами - дерево и, естественно, не содержит циклов.

Для начала, я бы упросил задачу. Например, посчитал бы сумму расстояний от одной произвольной вершины до P. Тут можно поспользоваться тем фактом, что граф связный, то есть из любой его вершины можно дойти до любой. Таким образом, используя поиск в ширину, можно нвйти минимальные расстояния от вершины до P за линейное время (кол-во вершин + кол-во ребер). Код нв Java

public  static int GetDistSum(ArrayList<Integer>[] graph, HashSet<Integer> p, int from)
{
    Queue<Integer> q = new LinkedList<>();
    boolean[] visited = new boolean[graph.length];
    int steps = 0;
    int sumSteps = 0;
    int pVisited = 0;
    q.add(from);
    while (q.isEmpty() == false)
    {
        int levelCount = q.size();
        for(int i=0; i<levelCount; i++)
        {
            int v = q.poll();
            if (visited[v]) continue;
            visited[v] = true;
            if (p.contains(v)) {
                sumSteps+=steps;
                pVisited++;
                if (pVisited == p.size()) return sumSteps;
            }
            for(Integer c : graph[v])
            {
                if (visited[c]) continue;
                q.add(c);
            }
        }
        steps++;
    }
    return sumSteps;
}

Ну и теперь осталось пройти по всем вершинам и найти минимум.

public static int GetMinDist(ArrayList<Integer>[] graph, int[] p)
{
    HashSet<Integer> pset = new HashSet<>();
    for(int i : p) pset.add(i);
    int min = Integer.MAX_VALUE;
    for(int i=1; i<graph.length; i++)
        min = Math.min(min, GetDistSum(graph, pset, i));
    return min;
}

То есть в результате сложность алгоритма будет N*(N+G), где N - колв вершин, G - колво ребер. Но мы и так значем, что ребер будет N-1, то есть сложность становится N(N+N-1) = 2N^2, то есть квадратичная.

Пример вызова для случая из вопроса:

public static void main(String[] args) {    
    ArrayList<Integer>[] graph = new ArrayList[9];
    for(int i=0; i<graph.length; i++) graph[i] = new ArrayList<>();
    graph[1].add(2);
    graph[2].add(1);
    graph[1].add(3);
    graph[3].add(1);
    graph[1].add(4);
    graph[4].add(1);
    graph[4].add(5);
    graph[5].add(4);
    graph[4].add(6);
    graph[6].add(4);
    graph[5].add(7);
    graph[7].add(5);
    graph[5].add(8);
    graph[8].add(5);
    int[] p = {2, 5, 6, 7};
    System.out.println(GetMinDist(graph, p));
}

Так как граф ненаправленный, то каждое ребро добавляется в него дважды.

Результат:

6

У автора же проблема в том, что он вызывает BFS для каждой вершины P, что делает сложность в итоге кубической (если P=N).