Broken Tree

题意翻译

题面： 给定一棵有n个节点的树，其中一号点是根。每条边有重量和强度。如果一条边的强度小于这条边深度较大的点的子树内所有边重量和，则这条边会断裂。你可以降低一些边的重量，且被降低重量的边会损失等量的强度。每条边的最终重量必须为正整数，强度必须为非负整数。询问至少要降低多少重量，或者输出-1表示这棵树无论如何都会断裂。本题配有SPJ 输入格式： 第一行一个数n表示节点数量 接下来n-1行每行四个数x,y,w,p表示x是y的父亲节点;这条边的重量w以及强度p 输出格式： 如果不存在满足条件的树则输出-1 否则第一行输出一个数n表示节点数量 接下来n-1行每行四个数，格式同输入格式，表示最终树的形态 输出的树必须保证降低的重量和最小且没有边会断裂 由 @流风之回雪 提供翻译

题目描述

You are given a tree that has $ n $ vertices, which are numbered from $ 1 $ to $ n $ , where the vertex number one is the root. Each edge has weight $ w_{i} $ and strength $ p_{i} $ . Botanist Innokentiy, who is the only member of the jury of the Olympiad in Informatics, doesn't like broken trees. The tree is broken if there is such an edge the strength of which is less than the sum of weight of subtree's edges to which it leads. It is allowed to reduce weight of any edge by arbitrary integer value, but then the strength of its edge is reduced by the same value. It means if the weight of the edge is $ 10 $ , and the strength is $ 12 $ , then by the reducing the weight by $ 7 $ its weight will equal $ 3 $ , and the strength will equal $ 5 $ . It is not allowed to increase the weight of the edge. Your task is to get the tree, which is not broken, by reducing the weight of edges of the given tree, and also all edged should have the positive weight, moreover, the total weight of all edges should be as large as possible. It is obvious that the strength of edges can not be negative, however it can equal zero if the weight of the subtree equals zero.

输入输出格式

输入格式

The first line contains the integer $ n $ ( $ 1<=n<=2·10^{5} $ ) — the number of vertices in the tree. The next $ n-1 $ lines contains the description of edges. Each line contains four integers $ x $ , $ y $ , $ w $ , $ p $ ( $ 1<=x,y<=n,1<=w<=10^{9},0<=p<=10^{9} $ ), where $ x $ and $ y $ — vertices which connect the edge (the vertex number $ x $ is the parent of the vertex number $ y $ ), $ w $ and $ p $ are the weight and the strength of the edge, accordingly. It is guaranteed that the edges describe the tree with the root in the vertex $ 1 $ .

输出格式

If it is impossible to get unbroken tree from the given tree, print -1 in the only line. Otherwise, the output data should contain $ n $ lines: In the first line print the number $ n $ — the number of vertices on the tree. In the next $ n-1 $ lines print the description of edges of the resulting tree. Each line should contain four integers $ x $ , $ y $ , $ w $ , $ p $ ( $ 1<=x,y<=n,1<=w<=10^{9},0<=p<=10^{9} $ ), where $ x $ and $ y $ — vertices, which the edge connects (the vertex number $ x $ is the parent of the vertex number $ y $ ), $ w $ and $ p $ are the new weight and the strength of the edge, accordingly. Print edges in the same order as they are given in input data: the first two integers of each line should not be changed.

输入输出样例

输入样例 #1

3
1 3 5 7
3 2 4 3

输出样例 #1

3
1 3 5 7
3 2 4 3

输入样例 #2

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

输出样例 #2

-1

输入样例 #3

5
1 2 2 4
2 4 1 9
4 5 5 6
4 3 4 8

输出样例 #3

5
1 2 2 4
2 4 1 9
4 5 1 2
4 3 2 6

输入样例 #4

7
1 2 5 2
2 3 4 3
1 4 3 7
4 5 4 1
4 6 3 2
6 7 1 6

输出样例 #4

7
1 2 5 2
2 3 2 1
1 4 3 7
4 5 3 0
4 6 3 2
6 7 1 6

题意翻译

题面： 给定一棵有n个节点的树，其中一号点是根。每条边有重量和强度。如果一条边的强度小于这条边深度较大的点的子树内所有边重量和，则这条边会断裂。你可以降低一些边的重量，且被降低重量的边会损失等量的强度。每条边的最终重量必须为正整数，强度必须为非负整数。询问至少要降低多少重量，或者输出-1表示这棵树无论如何都会断裂。本题配有SPJ 输入格式： 第一行一个数n表示节点数量 接下来n-1行每行四个数x,y,w,p表示x是y的父亲节点;这条边的重量w以及强度p 输出格式： 如果不存在满足条件的树则输出-1 否则第一行输出一个数n表示节点数量 接下来n-1行每行四个数，格式同输入格式，表示最终树的形态 输出的树必须保证降低的重量和最小且没有边会断裂 由 @流风之回雪 提供翻译