Прошу решить задачу на любом языке

Question

Прошу решить задачу на любом языке

Meps Mepsikovich Ученик (52), на голосовании 5 дней назад

В марте 1945 года, с целью предотвращения быстрого захвата советскими войсками города Берлина, Борману было поручено уничтожить максимальное количество дорог в городе, при этом оставив возможность перемещения между любыми двумя ключевыми пунктами.

Проект был реализован, и по состоянию на конец марта 1945 года в Берлине имеется
n
ключевых пунктов, пронумерованных целыми числами от 1 до n , и n − 1
двунаправленная дорога между ними. От любого пункта можно добраться до любого другого, используя эти дороги. Но в руководстве рейха быстро поняли, что Борман так усложнил перемещение по городу, что это сильно сказывалось на важных перевозках Германии.

Штирлицу было поручено исправить эту ситуацию, выбрав некоторую пару ключевых пунктов, между которыми предстоит построить ещё одну дорогу, тем самым образуя кольцевое движение внутри Берлина. Штирлиц решил немедленно сообщить об этом в центр (советской разведке). Он тут же передал дорожный план Берлина в штаб и стал ждать ответа.

Вам, как самому опытному математику в штабе советской армии, было поручено посчитать количество способов выбрать пару ключевых пунктов так, чтобы образованное кольцевое движение проходило ровно через k ключевых пунктов.
Формат выходных данных
Выведите одно целое число — количество способов построить дорогу между двумя ключевыми пунктами, создав таким образом кольцевое движение, проходящее через
k
ключевых пунктов.
Пример 1
Входные данные

7 3
1 2
1 3
2 4
2 5
2 6
3 7
Выходные данные

8
Пример 2
Входные данные

7 4
1 2
1 3
2 4
2 5
2 6
3 7
Выходные данные

4

Answer 1

На

 def count_ways_to_build_road(n, k, roads): 
    from collections import defaultdict 
 
    graph = defaultdict(list) 
    for u, v in roads: 
        graph[u].append(v) 
        graph[v].append(u) 
 
    def dfs(node, parent): 
        subtree_size[node] = 1 
        for neighbor in graph[node]: 
            if neighbor == parent: 
                continue 
            dfs(neighbor, node) 
            subtree_size[node] += subtree_size[neighbor] 
 
    subtree_size = [0] * (n + 1) 
    dfs(1, -1) 
 
    result = 0 
    for u in range(1, n + 1): 
        for v in graph[u]: 
            if subtree_size[u] < subtree_size[v]: 
                size1 = subtree_size[u] 
                size2 = n - size1 
            else: 
                size1 = subtree_size[v] 
                size2 = n - size1 
 
            if k - 1 <= size1 and k - 1 <= size2: 
                result += 1 
 
    return result 
 
def main(): 
    n, k = map(int, input("Введите количество ключевых пунктов и размер цикла через пробел: ").split()) 
    roads = [] 
    print(f"Введите {n - 1} дороги в формате 'u v':") 
    for _ in range(n - 1): 
        u, v = map(int, input().split()) 
        roads.append((u, v)) 
 
    result = count_ways_to_build_road(n, k, roads) 
    print(f"Количество способов: {result}") 
 
if __name__ == "__main__": 
    main()

Answer 2

 import collections 
 
def solve(): 
    n, k = map(int, input().split()) 
    edges = [] 
    graph = collections.defaultdict(list) 
    for _ in range(n - 1): 
        u, v = map(int, input().split()) 
        edges.append((u, v)) 
        graph[u].append(v) 
        graph[v].append(u) 
 
    count = 0 
    for i in range(1, n + 1): 
        for j in range(i + 1, n + 1): 
             
            q = collections.deque([(i, [i])]) 
            visited = {i} 
             
            while q: 
                curr, path = q.popleft() 
                 
                if curr == j and len(path) == k: 
                    count +=1 
                    break 
                 
                for neighbor in graph[curr]: 
                    if neighbor not in visited: 
                        visited.add(neighbor) 
                        q.append((neighbor, path + [neighbor])) 
                         
    print(count) 
 
solve()