Препод сказал показать решение этой задачи до вторника, а я вообще даже не представляю как оно должно выглядеть...Помогите пожалуйста!!!

[mlgdanya]

Каждой твари по паре
Коллекционировать животных можно не только на Ноевом ковчеге, но и на дереве. А дерево, как известно из теории графов, является связным ациклическим графом. Иными словами, дерево состоит из n вершин и n-1 ребра между ними. Каждое ребро соединяет некоторые две вершины дерева. Из любой вершины дерева можно добраться по ребрам до любой другой. Также дерево не содержит циклов, т. е. нельзя построить путь по ребрам из некоторой вершины и вернуться в нее, не пройдя по одному и тому же ребру дважды.
Для расположения животных на нашем дереве сделано q гнезд, где q - четное число. Животным каждого вида предназначены два гнезда.
После расселения по дереву каждая пара одного вида может перемещаться по ребрам дерева между своими гнездами. Они не должны мешать другим видам, т. е. чтобы никакие два пути не имели общего ребра. При этом допускается пересечение путей в вершине. Вам необходимо разместить q/2 видов животных по гнездам таким образом, чтобы пути
животных одного вида удовлетворяли этому условию.(Желательно решать на Python/C++/PascalABC.NET/Java/C#/Rust)


Формат входных данных
В первой строке входных данных находится два целых числа n и q (2≤ n ≤ 2 • 10^5, 2≤n, q четно) — общее количество вершин в дереве и количество вершин, в которых расположены гнезда.
Во второй строке входных данных находятся q различных целых чисел m(i) (1≤ m(i) ≤ n) - номера вершин с гнездами.
В каждой из следующих n - 1 строк входных данных находится два целых u(i) и v(i) ( 1≤ v(i), v(i) ≤ n, u(i)≠v(i) ). Это означает, что между вершинами u(i) и v(i) в дереве проведено ребро.
Гарантируется, что ребра во входных данных образуют дерево.

Формат выходных данных
Выходные данные должны содержать q/2 строк.
В каждой строке должно содержаться два целых числа х(i) и у(i) (1 ≤ x(i), y(i)≤ n) - номера вершин, в которых будут располагаться гнезда i-го вида животных.
Все числа в выходных данных должны быть различны и должны представлять собой номера вершин с гнёздами.
Если разместить животных требуемым образом невозможно, выведите число -1.
Критерии оценивания:
Баллы начисляются за каждый тест в отдельности, но ряд тестов имеют специфическую структуру:
1. u(i) = i, v(i) = i+1
2. u(i) = 1, v(i) = i+1
3. n ≤ 3000, q≤6
4. q=n.
5. Нет дополнительных ограничений.

Ввод:
9 6
1 3 2 5 8 6
3 1
3 2
3 4
3 5
3 6
4 7
7 8
1 9
Вывод:
3 2
8 5
1 6

[BDA]

Если вообще ничего не представляете как делать по задаче, то лучше сразу создавайте тему во фрилансе с указанием языка программирования, сроков и вознаграждения.
При первом взгляде ничего лучше рекурсивного переборного алгоритма не приходит в голову. Начать перебирать все пути от первого гнезда до остальных. При выборе пути исключать ребра пути из дерева. Брать следующее оставшееся гнездо и перебирать пути из него. Если удалось выбрать пути между всеми гнездами, то печатать список. Если на текущем шаге не удалось найти путь ни в одно из гнезд, то возвращаться на шаг назад и выбирать другой путь для предыдущего гнезда. Но такой алгоритм для больших деревьев явно будет работать слишком долго.

[ViktorR]

Можно пойти и таким путём:
1. Выбрать корневой узел. Поскольку через корневой узел можно перебираться на другие ветви, то претендентом на корневой узел будет узел, от которого идёт максимум ветвей.
2. Просматриваем каждую ветвь на предмет наличия гнёзд.
3. Если число гнёзд на ветви чётное, то соседние пары отдаём под особь.
4. Если число гнёзд нечётное, то дальние от корня соседние пары отдаём под особь, а ближайшее к корню связываем с гнездом на ветви, где гнёзд нечётное число. Проход между такими гнёздами - через корень.

Как вариант, распределяем гнёзда по ветвям с числом гнёзд большим чем одно. Если число гнёзд нечётное, то оставляем свободными ближайшие к корню.
На следующем шаге распределяем особи по свободным гнёздам, которые будут соединяться через корень.

PS:

Баллы начисляются за каждый тест в отдельности, но ряд тестов имеют специфическую структуру:
1. u(i) = i, v(i) = i+1
2. u(i) = 1, v(i) = i+1
3. n ≤ 3000, q≤6
4. q=n.
5. Нет дополнительных ограничений.

Эта часть мне непонятна.

PSS: И да, если решение будет найдено, то не плохо бы его тут оставить.

[BDA]

Сообщение от ViktorR

Эта часть мне непонятна.

Это подсказки, какие тесты сделать для проверки решения.
1. u(i) = i, v(i) = i+1 - все вершины дерева на одной "линии" (например, 1-2-3-4-5);
2. u(i) = 1, v(i) = i+1 - все вершины дерева кроме первой связаны с первой (дерево в виде "звезды");
3. n ≤ 3000, q≤6 - много вершин, мало гнезд;
4. q=n - все вершины дерева являются гнездами.

[ViktorR]

Спасибо.
Так понимаю что вершины - это узлы?
У меня сложно с терминологией. Так знаю, что у графа может быть корень, узлы и рёбра.
Слово "вершина" у меня ассоциируется с горами (тут живу).

[BDA]

Да, узлы, вершины, точки - синонимы в данном случае.

[ViktorR]

Это на Python (условия на язык нет).
Немного повозился в Сети и составил скрипт, который строит дерево с узлами, помеченными как гнездо и выбирает корневой узел.

class Node():
    def __init__(self, data=None, nest=None):
        self.data = data   # Ключ узла - номер узла
        if nest == '+':    # Так сделано только для визуализации
            self.nest = nest  # '+' - узел-гнездо (или 0 - ноль)
                              # m - вид животного
        else:
            self.nest = ''    # не гнездо (или оставить None)
        self.children = [] # список узлов-соседей
    
    def set_animal(self, animal):
        self.nest = animal
    
    def __repr__(self, indent=""): # Для печати дерева
        return (indent + repr(self.data) + str(self.nest) + "\n"
                + "".join(child.__repr__(indent+"    ")
                          for child in self.children))

def create_tree(edges, nests):
    # Получить набор уникальных ключей
    node_keys = set(key for keys in edges for key in keys)
    
    # Создать словарь с экземплярами узлов для каждого ключа:
    nodes = {}
    for key in node_keys:
        nodes[key] = Node(key,'+') if key in nests else Node(key)

    # Заполнить дочерние атрибуты из edges - установить связи
    # Из списка ребер получаем номер родителя и номер дочернего узла
    for parent, child in edges:
        # Заполняем список узлов-соседей
        nodes[parent].children.append(nodes[child])
        # Удалить дочерние узлы из множества узлов
        # У нас останется только корневой элемент
        node_keys.remove(child)
    # Получить корень из набора, который на данный момент должен содержать только один элемент
    for root_key in node_keys:
        return nodes[root_key]


# Исходные данные
nests = [1, 3, 2, 5, 8, 6]       # Узлы-гнезда
edges = [[3,1],[3,2],[3,4],[3,5],[3,6],[4,7],[7,8],[1,9]] # Список ребер
root = create_tree(edges, nests) # Дерево

print(root)

В результате получается такое дерево (по исходным данным):

3+
    1+
        9
    2+
    4
        7
            8+
    5+
    6+

Далее можно размещать, но хочется и поспать ...

PS: Первичный код найден тут:
https://stackoverflow.com/questions/...tree-in-python

[Valick]

Уже среда, расходимся

[BDA]

Вот код для алгоритма из 2 сообщения:

from collections import defaultdict

def connect_nests_recursive(nests_set, edges_dict, res_list):
    nest = nests_set.pop()
    checked_nests = set()
    wave = edges_dict[nest]
    backtrace = {node: nest for node in wave}

    while len(wave) > 0:
        for another_nest in wave.intersection(nests_set):
            # exclude another_nest
            nests_set.remove(another_nest)

            if len(nests_set) == 0:
                res_list.append([nest, another_nest])
                return True

            # exclude path edges between nest and another_nest
            node = another_nest
            while node != nest:
                next_node = backtrace[node]
                edges_dict[node].remove(next_node)
                edges_dict[next_node].remove(node)
                node = next_node

            if connect_nests_recursive(nests_set, edges_dict, res_list):
                res_list.append([nest, another_nest])
                return True

            # include another_nest
            nests_set.add(another_nest)
            # include path edges between nest and another_nest
            node = another_nest
            while node != nest:
                next_node = backtrace[node]
                edges_dict[node].add(next_node)
                edges_dict[next_node].add(node)
                node = next_node

            checked_nests.add(another_nest)
        
        if checked_nests == nests_set:
            nests_set.add(nest)
            return False

        next_wave = set()
        for node in wave:
            for next_node in edges_dict[node].difference(set([backtrace[node]])):
                next_wave.add(next_node)
                backtrace[next_node] = node
        wave = next_wave

    nests_set.add(nest)
    return False

def connect_nests(nests, edges):
    nests_set = set(nests)

    edges_dict = defaultdict(set)
    for node1, node2 in edges:
        edges_dict[node1].add(node2)
        edges_dict[node2].add(node1)

    res = []
    if not connect_nests_recursive(nests_set, edges_dict, res):
        return [-1]
    else:
        return res

#-------------------------------------------------------------------------------

# example
nests = [1, 3, 2, 5, 8, 6]
edges = [[3, 1], [3, 2], [3, 4], [3, 5], [3, 6], [4, 7], [7, 8], [1, 9]]
print(connect_nests(nests, edges))

#-------------------------------------------------------------------------------

import itertools

# Note: graph isomorphism is not taken into account
def gen_tree_edges(n):
    res = []
    gen_tree_edges_recursive(3, n, [[[1, 2]]], res)
    return res

def gen_tree_edges_recursive(i, n, subres, res):
    if i > n:
        res.extend(subres)
        return
    for j in range(1, i):
        gen_tree_edges_recursive(i + 1, n, [v + [[j, i]] for v in subres], res)

for n in range(2, 11):
    for q in range(2, n + 1, 2):
        print("N", n, "Q", q)
        for nests in itertools.combinations(list(range(1, n + 1)), q):
            for edges in gen_tree_edges(n):
                if connect_nests(nests, edges) == [-1]:
                    print(nests, edges)

Для поиска гнезд используется волновой алгоритм, так что сначала пытаются объединиться в пару ближайшие гнезда. Проверил работу на всех деревьях (но изоморфизм графов практически не учтен) с количеством вершин N от 2 до 10 и количеством гнезд от 2 до N (только четные) и не нашел случая, когда гнезда невозможно распределить.

[ViktorR]

В своих рассуждениях полагал, что пересечения путей возможны только в корне. Но перечитал условие.
Пересечение путей может быть в любом узле. Но тогда сложно придумать дерево, на котором нельзя распределить пары животных. Если у двух пар есть общее ребро, то достаточно переставить гнёзда, которые соединены общим ребром.

Спасибо, попробую разобраться в вашем коде.
Авось что-то пригодится для студентов.

PS: Ваше решение, в другой теме, с вложенными циклами и else, и командами break и continue буду использовать.