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 i-th edge has two parameters associated with it, Ci denoting the cost of the edge and parameter Di.
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 i-th edge to X will be Di × |X - Ci|.
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.
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 ui, vi, Ci, Di denoting there is an edge between vertex ui and vi with parameters Ci and Di that are described in the statement.
For each test case, output N lines.
First line should contain an integer corresponding to minimum time required.
In next N - 1 lines, i-th line should contain the updated cost of i-th edge.
- 1 ≤ T, N ≤ 200000
- Denote the sum of N in all T test-cases with S
- S ≤ 200000
- 1 ≤ ui, vi ≤ N
- 1 ≤ Ci, Di ≤ 106
- 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) Di = 1 for all i
- Subtask #4 (50 points) original constraints
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
|Tags||binary-search, dynamic-programming, hard, kingofnumbers, oct16|
|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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.