填空题
树上最短链
发布于 2022-03-02 13:31:58
在一个地区有 
个城市以及 
条无向边，每条边的时间边权都是 
，并且这些城市是联通的，即这个地区形成了一个树状结构。每个城市有一个等级。
现在小强想从一个城市走到另一个不同的城市，并且每条边经过至多一次，同时他还有一个要求，起点和终点城市可以任意选择，但是等级必须是相同的。
，含义如题面所述。
第二行
个正整数 
，代表每个城市的等级。
接下来
行每行两个正整数 
，代表一条无向边。
保证给出的图是一棵树。
。
。
。输入样例：
3
1 2 1
1 2
2 3 输出描述：
仅一行一个整数代表答案，如果无法满足要求，输出 
。输出样例
2
个城市以及 条无向边，每条边的时间边权都是 ，并且这些城市是联通的，即这个地区形成了一个树状结构。每个城市有一个等级。现在小强想从一个城市走到另一个不同的城市，并且每条边经过至多一次，同时他还有一个要求，起点和终点城市可以任意选择，但是等级必须是相同的。
但是小强不喜欢走特别远的道路，所以他想知道时间花费最小是多少。
进阶：时间复杂度
，空间复杂度
输入描述：
第一行一个正整数 ，空间复杂度，含义如题面所述。第二行
个正整数 ，代表每个城市的等级。接下来
行每行两个正整数 ，代表一条无向边。保证给出的图是一棵树。
。 。。输入样例：
3
1 2 1
1 2
2 3 输出描述：
仅一行一个整数代表答案，如果无法满足要求，输出 。输出样例
2关注者
0
被浏览
16
