题目描述

给一棵 $n$ 个点、带边权的树，刚开始每个点都是白色。现在需要在选择一些点染黑、使得如下限制得到满足:

• 对于每个点 $u$ ，至少有一个黑点距离 $u$ 不超过 $d[u]$

现在给出在每个点的约束 $d[u]$ ，以及把每个点染黑的花费 $c[u]$ ，请你选择一些点染黑，使得每个点的约束得到满足，并且总花费最小。

输入格式

第一行一个整数 $t$ ，代表有 $t$ 组数据。

对于每组数据，第一行一个整数 $n$ 。

接下来一行 $n$ 个正整数 $c[i]$ 。

接下来一行 $n$ 个正整数 $d[i]$. 接下来 $n-1$ 行，每行三个正整数 $(u, v, w)$ ，代表树上一条边。

输出格式

对于每组数据输出一行一个整数，代表最小总花费。

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

2
1
2
2
3

数据规模与约定

对于所有测试点， $t \leq 10,1 \leq n \leq 10^3, 1 \leq d, c, w \leq 10^9$ 。

• 子任务1 (15分) : $n \leq 20$
• 子任务2 (15分) : 成链 $(u=v-1)$
• 子任务3 (15分)：菊花 $(u=1)$
• 子任务4 (15分) : $d, w=1$
• 子任务5 (20分) : $w=1$ ，且所有 $c$ 都相等
• 子任务6 (10分) : $w \leq 10^3$
• 子任务7 (10分)：无特殊限制

大样例

大样例下载