首页 > 试题广场 >

树上最短链

[编程题]树上最短链
  • 热度指数：2446 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
在一个地区有 个城市以及 条无向边，每条边的时间边权都是 ，并且这些城市是联通的，即这个地区形成了一个树状结构。每个城市有一个等级。
现在小强想从一个城市走到另一个不同的城市，并且每条边经过至多一次，同时他还有一个要求，起点和终点城市可以任意选择，但是等级必须是相同的。
但是小强不喜欢走特别远的道路，所以他想知道时间花费最小是多少。

进阶：时间复杂度，空间复杂度

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


输出描述:
仅一行一个整数代表答案，如果无法满足要求，输出  。
示例1

输入

3
1 2 1
1 2
2 3

输出

2
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 阿里巴巴 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 信息技术岗 区块链 测试开发工程师 大数据开发工程师 数据分析师 Java工程师
上传者：小小
难度：
0条回答 7284浏览

热门推荐

通过挑战的用户

相关试题

树上最短链

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号