U462577 捉晶蝶

JKQ 杯 2026/05/11 T8（CF2500）。

你和魔女 C 回到了魔女协会，协会的花园里有一颗巨大的苹果树，树上一共 $n$ 个苹果，由 $n - 1$ 根树枝分叉形成一棵树的结构。每个苹果上都有 $1$ 只小晶碟，美丽值为 $w_i$，但小晶碟十分怕人，如果有人在点 $f$，则 $f$ 的儿子节点 $v_j$ 上的小晶碟会分别在 $t_{v_j}(\in \{1, 2, 3\})$ 秒后消失。 你现在在树底部，也就是节点 $1$（晶蝶刚刚受惊），你可以一秒走一个枝干，每到一个点就能瞬间捉到该点的晶碟，并且你可以使**一个**点上的晶蝶被禁锢，从而**不会消失**（可以不用）。你想捉到的晶蝶美丽值之和**最大**（时间不限）。数据多测。

输入第 $1$ 行只有一个正整数 $T$，表示数据组数。 每组输入第 $1$ 行有 $1$ 个整数 $n$，表示苹果个数。 之后 $n - 1$ 行每行 $2$ 个整数 $u,v$，一条树干分支的起点，终点。 第 $n + 1,n + 2$ 行分别有 $n$ 个整数 $t_i$ 和 $w_i$，表示苹果上晶蝶受惊后存在的秒数及表示苹果上晶蝶的美丽值。

输出有 $T$ 行，一行一个数，表示捕捉的晶蝶美丽值之和最大值。

### 【样例解释 #1】: 树的图是这样的（黄色是 $t_i$，红色是 $w_i$）： 禁锢点 $2$ 的晶蝶即可将晶蝶全部抓住。 ### 【样例解释 #2】: 禁锢点 $2$ 的晶蝶（或不使用）即可将晶蝶全部抓住。 | 测试点 | $T$ | $n$ | | :---: | :---: |:---:| |$1 \sim 2$|$\le 10$|$\le 20$| |$3 \sim 9$|$\le 10 ^ 3$|$\le 10^ 3$| |$10 \sim 15$|$\le 20$|$\le 10 ^ 5$| |$16 \sim 20$|$\le 10 ^ 4$|$\le\ 5 \times 10 ^ 5$| 对于 $100\%$ 的数据，$1 \le T \le 10 ^ 4,1 \le n \le 5 \times 10 ^ 5,1 \le \sum n \le 10 ^ 6,1 \le t_i \le 3,1 \le w_i \le 10 ^ 9$。 附件样例满足 $T = 20, 1 \le n \le 10$.