首页 > 试题广场 >

树上子链

[编程题]树上子链
给定一棵树 T ，树 T 上每个点都有一个权值。
定义一颗树的子链的大小为：这个子链上所有结点的权值和 。
请在树 T 中找出一条最大的子链并输出。

输入描述:
第一行输入一个 。
接下来一行包含n个数，对于每个数 ，表示 i 结点的权值。
接下来有n-1行，每一行包含两个数u，v（  , u != v），表示u与v之间有一条边。


输出描述:
仅包含一个数，表示我们所需要的答案。
示例1

输入

5
2 -1 -1 -2 3
1 2
2 3
2 4
2 5

输出

4

说明

样例中最大子链为1 -> 2 -> 5

备注:
一个结点，也可以称作一条链
算法知识视频讲解
添加回答

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

提交观点

问题信息

难度：
0条回答 7浏览

热门推荐

相关试题

树上子链

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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