Tree Balancing

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
You are given a rooted tree of N vertices, the root is at vertex 1. The ith edge has two parameters associated with it, C_{i} denoting the cost of the edge and parameter D_{i}.
You want to make cost of all the paths from the root to any leaf having equal costs. Cost of a path is sum of costs of all the edges on the path. For that, you can increase or decrease cost of any edge. The time taken in changing cost of ith edge to X will be D_{i} × X  C_{i}.
Find the minimum time required to make cost of all the paths from the root to all leaves equal. Furthmore, you should also output the new edge costs. If there are more than one possible solutions, you can print any of them.
Note that you can change costs of edges to negative, but all costs should be integers.
Input
First line of input contains an integer T denoting number of test cases. T test cases follow.
First line of each test case contains an integer N denoting number of vertices in the tree.
Each of the next N  1 line contains four space separated integers u_{i}, v_{i}, C_{i}, D_{i} denoting there is an edge between vertex u_{i} and v_{i} with parameters C_{i} and D_{i} that are described in the statement.
Output
For each test case, output N lines.
First line should contain an integer corresponding to minimum time required.
In next N  1 lines, ith line should contain the updated cost of ith edge.
Constraints
 1 ≤ T, N ≤ 200000
 Denote the sum of N in all T testcases with S
 S ≤ 200000
 1 ≤ u_{i}, v_{i} ≤ N
 1 ≤ C_{i}, D_{i} ≤ 10^{6}
Subtasks
 Subtask #1 (10 points) S ≤ 200, all nodes except node 1 are direct children of node 1
 Subtask #2 (20 points) S ≤ 200
 Subtask #3 (20 points) D_{i} = 1 for all i
 Subtask #4 (50 points) original constraints
Example
Input: 1 5 1 2 5 4 1 3 15 15 2 4 3 2 2 5 5 1 Output: 19 5 15 10 10
Author:  kingofnumbers 
Editorial  http://discuss.codechef.com/problems/TREEBAL 
Tags  binarysearch, dynamicprogramming, hard, kingofnumbers, oct16 
Date Added:  30092016 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 