首页 > 试题广场 >

树上最短链

[编程题]树上最短链

热度指数：2416 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在一个地区有 $\mathit n$ 个城市以及 $\mathit n-1$ 条无向边，每条边的时间边权都是 $\text 1$ ，并且这些城市是联通的，即这个地区形成了一个树状结构。每个城市有一个等级。
现在小强想从一个城市走到另一个不同的城市，并且每条边经过至多一次，同时他还有一个要求，起点和终点城市可以任意选择，但是等级必须是相同的。

但是小强不喜欢走特别远的道路，所以他想知道时间花费最小是多少。

进阶：时间复杂度 $O(n^2logn)\$ ，空间复杂度 $O(n)\$

输入描述:

第一行一个正整数 ，含义如题面所述。
第二行  个正整数 ，代表每个城市的等级。
接下来  行每行两个正整数 ，代表一条无向边。
保证给出的图是一棵树。
 。
 。
。

输出描述:

仅一行一个整数代表答案，如果无法满足要求，输出  。

示例1

输入

输出

算法知识视频讲解

Python

yyyywwwwqqqq

import collections
n = int(input())
edge = [[] for i in range(n)]
a=list(map(int, input().split()))
for i in range(n-1):
    x,y = map(int, input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
ans = n
d = collections.defaultdict(list)
for i in range(n):
    d[a[i]].append(i)
if len(d)==len(a):
    print(-1)
else:
    for k,v in d.items():
        if len(v)==1:
            continue
        else:
            for root in v:
                stack = [root]
                deep = 0
                visited=set()
                while stack:
                    tmp = []
                    while stack:
                        node = stack.pop()
                        visited.add(node)
                        if a[node]==a[root] and node!=root:
                            ans = min(ans, deep)
                            break
                        for i in edge[node]:
                            if i not in visited:
                                tmp.append(i)
                    deep+=1
                    stack = tmp.copy()
                    if deep>=ans:
                        break
    print(ans)

发表于 2021-08-02 11:05:56 回复(0)