问题 5050 -- 平衡的树

5050: 平衡的树

题目描述

  给定一棵 $n$ 个结点的有根树,结点从 $1$ 到 $n$ 编号,根为 $1$ 号结点。每条边有两个权值 $a_i,b_i$,其中 $a_i$ 是正整数,$b_i$ 是非负整数。
如果对于树上的每条边 $(u,v)$($u$ 是 $v$ 的父亲),都满足 $v$ 子树中所有边的权值 $a$ 之和不超过边 $(u,v)$ 的权值 $b$,则我们称这棵树是平衡的。
你可以花费 $1$ 的代价将某条边的 $a$ 和 $b$ 同时减少 $1$,但你不能让 $a<0$ 或 $b<0$。
你需要用最小的代价让原树变得平衡。

输入

第一行一个正整数 $n$,表示结点数。
接下来 $n-1$ 行,每行四个整数 $u,v,a,b$,描述了一条边。保证 $u$ 是 $v$ 的父亲。

输出

如果无法使原树平衡,输出一行 -1;
否则输出一行一个非负整数,表示使原树平衡的最小代价。

样例输入输出

输入#1 复制
5
1 2 2 4
2 4 1 9
4 5 5 6
4 3 4 8
输出#1 复制
6
输入#2 复制
4
1 3 2 3
3 4 5 1
3 2 3 3
输出#2 复制
-1

提示

对于 $30\%$ 的数据,$n \leq 10, \prod a_i \leq 1000$;
对于 $70\%$ 的数据,$n \leq 1000$;
对于 $100\%$ 的数据,$1 \leq n \leq 2 \times 10^5$,$1 \leq u,v \leq n$,$1 \leq a \leq 10^9$,$0 \leq b \leq 10^9$。

序号 标题 作者 发表时间 费用 订购数 操作