1008. 水豚噜噜的平衡树

题目描述

可爱的水豚噜噜走在树下，可是雨滴从树上掉到它的大大的脸上。噜噜有一个想法，有没有可能雨滴在树上是平衡的，就不会砸到它？由于你也很喜欢可爱的噜噜，所以你要帮它解决这道题。

给定一棵有 $n$ 个点的树。第 $i$ 个点初始有 $a_i$ 单位水滴，并且最终至多能够容纳 $b_i$ 单位水滴。

同时给出一个长度为 $n$ 的排列 $p$，其中 $p_i$ 表示点 $i$ 的镜像点。输入保证树和映射 $p$ 满足：

1. $p_{p_i}=i$；
2. 对任意树边 $u-v$，$p_u-p_v$ 也是树边；
3. 对称中心恰好为以下两种情况之一：
   • 存在唯一的点 $c$ 满足 $p_c=c$；
   • 不存在固定点，并且存在唯一的边 $x-y$ 满足 $p_x=y,p_y=x$。

每条边 $u-v$ 有一个运输系数 $w$。

一次操作可以选择一条边 $u-v$ 和一个正整数 $x$，把 $x$ 单位水滴从一个端点移动到另一个端点。操作过程中任意点的水滴数都不能为负，本次操作的代价为

你需要进行若干次操作，使最终水滴数 $c_i$ 满足：

并且对所有点 $i$ 都有

求最小总代价。若不存在合法方案，输出 $-1$。

注意：初始与过程中水滴数 $a_i$ 可以大于容量 $b_i$，容量限制只针对最终状态。

输入格式

第一行一个整数 $T$，表示测试数据组数。

对于每组数据：

• 第一行一个整数 $n$；
• 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$；
• 第三行 $n$ 个整数 $b_1,b_2,\ldots,b_n$；
• 第四行 $n$ 个整数 $p_1,p_2,\ldots,p_n$；
• 接下来 $n-1$ 行，每行三个整数 $u,v,w$，表示树边 $u-v$ 的运输系数为 $w$。

并且对每组数据均保证

输入保证树与镜像映射 $p$ 满足题目描述中的全部性质。

输出格式

对于每组数据输出一行一个整数，表示最小总代价；若无解，输出 $-1$。

样例输入

4
4
0 10 0 0
10 10 10 10
4 3 2 1
1 2 1
2 3 1
3 4 1
3
0 4 0
0 4 4
1 3 2
1 2 100
1 3 1
2
1 0
10 10
2 1
1 2 9
1
7
6
1

样例输出

5
202
-1
-1

来源：2026杭电多校-测试专用（杭电第1场-内测） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1237&pid=1008