题目内容

某通信网由 $n$ 个基站构成一棵有根树，编号为 $1$ 到 $n$，其中 $1$ 号为总控站（根）。每个基站有一个整数收益 $r_i$，以及一次关停费用 $c_i$：支付 $c_i$ 后可将该基站收益置为 $0$。

还可以对树边执行拆缆：支付该边的拆缆费用后切断这条边，此后与总控站不再连通的基站全部移出网络。

操作结束后，保留下来的是包含总控站的连通块。其净收益定义为：连通块内各基站最终收益之和，减去关停与拆缆支付的总费用。

每个基站至多关停一次；每条边可选择拆或不拆。也可以什么都不做，此时连通块为整棵树，净收益为全部收益之和。

请计算总控站所在连通块能达到的最大净收益。

节点数 $n$ 不超过 $5 \times 10^5$。每个收益 $r_i$ 的绝对值不超过 $10^6$，关停费用 $c_i$ 与拆缆费用均为不超过 $10^6$ 的正整数。

输入描述

第一行输入一个整数 $n$，表示基站数量，满足 $1 \le n \le 5 \times 10^5$。 第二行输入 $n$ 个整数 $r_1, r_2, \dots, r_n$，表示各基站收益，满足 $-10^6 \le r_i \le 10^6$。 第三行输入 $n$ 个正整数 $c_1, c_2, \dots, c_n$，表示各基站关停费用，满足 $1 \le c_i \le 10^6$。 接下来 $n-1$ 行，每行三个整数 $u$、$v$ 和 $d$，表示基站 $u$ 与 $v$ 之间有一条边，拆缆费用为 $d$，满足 $1 \le u, v \le n$，$u eq v$，$1 \le d \le 10^6$。 保证这 $n$ 个基站构成一棵连通无环图，根为 $1$ 号基站。

输出描述

输出一个整数，表示经过关停与拆缆后，总控站所在连通块能获得的最大净收益。

样例1

输入

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

输出

12

说明

一种最优策略是不拆任何光缆，而对 $3,4,5$ 号基站分别支付关停费用 $1$，使它们收益变为 $0$。 保留收益为 $10+5+0+0+0=15$，总费用 $3$，净收益 $12$。 若切断 $1$-$3$ 边（费用 $4$）并关停 $3$ 号，只能得到 $10$，更差。

样例2

输入

7
5 4 -10 3 -2 -8 4
2 3 4 1 1 2 1
1 2 3
1 3 2
2 4 1
2 5 1
3 6 4
3 7 3

输出

9

说明

对每个子站比较「拆缆」与「保留该子树」的贡献，再对自身比较「保留收益」与「支付关停费用」。 按后序动态规划得到总控站的最大净收益为 $9$。

样例3

输入

1
5
3

输出

5

说明

只有总控站一个基站，收益 $5$，关停费用 $3$。关停得到 $-3$，不如直接保留 $5$。没有边可拆，答案为 $5$。

样例4

输入

3
-5 10 -8
1 2 1
1 2 3
2 3 100

输出

8

说明

$3$ 号关停贡献 $-1$，优于保留 $-8$，也远优于拆 $2$-$3$（费用 $100$）。 $2$ 号保留收益 $10$ 并带上 $-1$，贡献 $9$。 总控站关停（$-1$）并保留 $2$ 号子树，净收益 $8$，优于保留自身负收益。