You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

宁静的森林里有一棵生命之树，这棵树有 $n$ 个节点，每个节点都是维持这片森林生态系统的关键组成部分。

然而，最近一次的自然灾害令生命之树受到了损伤，于是生态学家们提出了一个保护方案，选择一些节点注入生命露滴，以确保：

• 对于每个节点 $u$，至少有一个注入生命露滴的节点距离 $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分）：$1\leq 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分）：无特殊限制