Shivam has started a new startup named Developer’s Incorporation. In this startup every project is broken down into a hierarchy of modules. The modules are numbered from 1 to N. The hierarchy of modules is represented as a tree with root as a Module 1.
Agile Development Process is followed in Developer’s Incorporation. More specifically XP(Extreme Programming) framework is adopted. You can read about XP framework here
Pair programming is a key feature of XP. In Pair programming people work in a team of 2 In Developer’s Inc , a single XP team comprises of a Developer and a Tester, Developer is responsible for coding and construction of modules allotted to them, while the Tester is responsible for testing and debugging those modules.
Also this team functions in a unique way. Developer develops/codes modules allotted to their team in any order and Tester tests/debugs them in any order with few rules:
- Developer if starts coding a module, does not stop until the module is completely coded(works on a single module at a time).
- Developer can work on the allotted modules in any order.
- Tester if starts with a module, does not stop until the module is completely tested.(works on a single module at a time).
- Tester can test the modules in any order but he can test only those modules which have been completely developed.
Each module is associated with CT(Time required to code the Module ) and TT(Time required to test and debug the module).
A single XP team is allotted for each hierarchical level of modules.A team does not start its operation until and unless all the modules below its hierarchy are completely coded and tested.
Find the minimum time which is required to completely test and debug all the modules.
- The first line of the input contains an integer T denoting the number of test cases . The description of T testcases follow.
- The first line of each test contain a single Integer N denoting the number of modules
- The following N-1 lines contain 2 space seperated integers denoting the edges of the hierarchy tree .
- The next N line contains 2 space seperated integers denoting CTi and TTi
For each test case, Print the minimum time required to complete all modules.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 100000
- 1 ≤ u,v ≤ N
- 1 ≤ CTi, TTi ≤ 100000
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions