美团笔试

3.18美团笔试第五题怎么做啊?看了代码也不是很懂,有大佬指点一下嘛

题目5:

题目描述:

现在有若干节点。每个节点上有能量塔。所有节点构成一棵树。

某个节点u可以为和u距离不超过给定值的节点各提供一点能量。

此处距离的定义为两个节点之间经过的边的数量。特别的,节点u到本身的距离为零。



现在给出每个书点上的能量塔可以为多远的距离内的点提供能量。

小美想要探究每个节点上的能量值具体是多少。你的任务是帮助小美计算得到,并依次输出。



输入描述

第一行个整数N,表示节点的数量。

接下来一行N个以空格分开的整数,依次表示节点1,节点2,….节点N的能量塔所能提供能量的最远距离。

接下来N-1行,每行两个整数,表示两个点之间有一条边。

1≤N≤500,节点上能量塔所能到达的最远距离距离不会大于500.



输出描述

一行N个整数,依次表示节点1,节点2,...,节点N上的能量值。



输入样例

3

1 1 1 

1 2 

2 3



输出结果

2 3 2
全部评论
floyd或者lca求出任意两节点间的距离
点赞 回复 分享
发布于 2023-04-09 21:23 北京

相关推荐

牛客769922382号:轮到大佬给公司发感谢信了,想想就爽
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务