Treeland Exhibition 的算法

Question

Problem Description
There are n towns in the treeland – they form a tree, as you may guess, i.e. there is a unique path between every pair of towns. The length of road connecting every pair of adjacent towns is always 1 unit.

You want to hold an exhibition simultaneously on no more than L+1 consecutive towns, i.e. you choose two towns u and v of no more than L unit apart, and set up your exhibition in all the towns on the unique path from u to v. You want to attract people from all over the treeland to your exhibition, so you’d like to minimize the sum of “travelling distance” from every town. The “travelling distance” of a town is the distance from that town to its closest exhibition-town.

Input
There are at most 25 test cases. Each case begins with two integers, n and L (n <= 10000, 0 < L <= 100), the number of towns, and the maximal distance of the “endpoint towns” you choose. Next n-1 lines contain the descriptions of connections, each with two integers a and b, indicating that town a and town b are directly connected (towns are numbered from 0 to n-1). The input ends with n = L = 0.

Output
For each test case, print the minimal sum of travelling distance.

Sample Input
3 1
0 1
1 2
4 1
0 1
1 2
2 3
0 0

Sample Output
1
2

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

# 读取数据
input = readLines()

# 解析输入
n = int(input[1])
L = int(input[2])

if n == L == 0:
    ans = 0
else:
    # 构建邻接表
    graph = [[] for _ in range(n)]
    for line in input[3:]:
        a, b = map(int, line.split())
        graph[a].append(b)
        graph[b].append(a)

    # 距离计算
    def dijkstra(start):
        dist = [float('inf')] * n
        prev = [-1] * n
        dist[start] = 0
        queue = [(0, start)]

        while queue:
            cur_dist, node = heappop(queue)
            if cur_dist > dist[node]:
                continue

            for next_node in graph[node]:
                new_dist = cur_dist + 1
                if new_dist < dist[next_node]:
                    dist[next_node] = new_dist
                    prev[next_node] = node
                    heappush(queue, (new_dist, next_node))

        return dist, prev

    # 找到起点与终点的最短距离和前驱节点
    start, end = dijkstra(0)[0]
    start_prev = dijkstra(start)[1][end]

    # 计算最小总距离
    total_distance = 0
    for i in range(1, n - 1):
        current_distance = 0
        while True:
            if start_prev[i] != -1:
                current_distance += 1
                start = start_prev[i]
                start_prev[i] = -1
            else:
                break
        total_distance += current_distance
    ans = total_distance

print(ans)