E-筑巢_牛客小白月赛45

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小沙转生成为了蚂蚁子，现在他攻占了一颗树，树里面还是实心的木头，所以小沙想要将里面连续的一部分掏空让自己居住（因为小沙只想住一个家）。但是并不是每个部分都适合开采，某些地方的开采后可能导致舒适度下降。

将上面的问题抽象出来，我们可以理解成，给定你一个n个节点的树，你需要在树上选取一个非空连通块，使其舒适度和最大。选择的边和点的舒适度都是舒适度。

第一行输入一个正整数数 $n\leq 10^5$

第二行输入n个数每个数代表该节点开采后的舒适度 $-10^9\leq a_i\leq 10^9$

随后n-1行每行输入3个数x,y,w分别代表x与y之间有一条舒适度为w的路

$1\leq x,y\leq n,-10^9\leq w\leq 10^9$

输出小沙的家的最大舒适度

示例1

复制

复制