题解

题目描述

给定一棵根为节点1的树，每个节点有权值$r_i$和中和成本$c_i$。可以选择切断边（支付代价$d$）或中和节点（支付$c_i$使收益为0）。求根所在连通块的最大净收益（总收益减去操作代价）。

思路分析

树形动态规划：后序遍历每个节点，计算在保留该节点时，中和或不中和的最大贡献，并处理子节点的切断或保留决策。

题目内容

给定一棵有根树，节点编号为 $1$ ~ $n$ ，其中节点 $1$ 为根节点。

每个节点都有一个整数收益 $r_i$ 。

此外，每个节点还附带一个中和成本 $c_i$ ，表示你可以花费 $c_i$ 的代价将该节点的收益置为 $0$ (即忽略该节点原有的收益)。

你还可以花费一定代价对树上的边进行切断操作。对任一边，你可以支付该边的切断代价，从而切断这条边，切断后，与根节点不再连通的部分将被移除。

经过一系列操作后，最终会得到包含根节点的一个连通块。该连通块的净收益定义：连通块内所有节点的(最终)收益之和减去你为执行中和操作和切断操作支付的总代价。

请你计算，在允许选取任意操作方案的情况下，根节点所在的连通块所能获得的最大净收益是多少。

注意：

• 对于任一节点，你最多只能对其执行一次中和操作。

• 对于每一条边，你可以选择是否切断，切断操作一经使用，该边及其下游所有节点均不计入连通块收益。

你可以不做任何操作，此时连通块即为整棵树，其净收益为所有节点收益之和。

【名词解释】

• 树上联通块：树上联通块是指树上的一些节点组成的集合，这些节点之间通过树上的边相连，并且任意两个节点之间有且仅有一条路径。

输入描述

第一行输入一个整数 $n(1≦n≦5×10^5)$ 表示树的节点数量。

第二行输入 $n$ 个整数 $r _1,r_2,…,r_n(-10^6≦r_i≦ 10^6)$ 表示各节点的收益。

第三行输入 $n$ 个正整数 $c_1,c_2,…,c_n(1≦c_i≦ 10^6)$ 表示各节点的中和成本。

接下来 $n-1$ 行，每行输入三个整数 $u,v$ 和 $d(1≦u,v≦n,u≠v,1≦d≦10^6)$ ，表示节点 $u$ 与节点 $v$ 之间存在一条边，该边的切断代价为 $d$ 。

保证输入的 $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

说明

一种策略为：

• 不对根节点 $1$ 及节点 $2$ 进行中和作；

• 对节点 $3$ 执行中和操作，即支付 $1$ ，令 $r_3$ 变为 $0$ ；

• 不对节点 $4$ 和节点 $5$ 执行中和操作；

• 对边 $(1,3)$ 执行切断操作，支付代价 $4$ ，从而移除节点 $3,4,5$ 。

剩余连通块仅包含节点 $1$ 与节点 $2$ ，其总收益为 $10+5=15$ ，减去操作总费用 $1+4=5$ ，净收益为 $15-5=10$ 。

另一种更优策略为：

• 不切断边 $(1,3)$ ，而对节点 $4$ 和节点 $5$ 各自执行中和操作，分别支付 $1$ ;

• 同时对节点 $3$ 执行中和操作，支付 $1$ 。

此时所有节点的最终收益为：$10,5,0,0,0$ ，总和为 $15$ ，操作总费用为 $1+1+1=3$ ，净收益为 $15-3=12$ 。

因此最大净收益为 $12$ 。

样例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