Traffic in Chefland
All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
There are N cities in Chefland. Chef owns the biggest traffic company in Chefland, and Chef has built N-1 bidirectional roads between these cities. The i-th road connects city ai and city bi, and is ci kms long. It's possible to travel between any two cities by going through these roads. However, only those people who have Chef's VIP card can use these roads. It costs 1 Chefcoin/km to travel on one of Chef’s roads.
A businessman named Fehc came to Chefland to compete with Chef's company and created his own traffic network. It also contains N-1 roads. The i-th of these roads connects city pi and city qi, and has length ri kms. Again, it is possible to travel between any two cities by going through Fehc's roads (and ignoring Chef's). Similar to Chef, only those people who have Fehc's VIP card can travel on these roads and it costs 1 Chefcoin/km to travel on one of Fehc's roads.
On New Year's Day in Chefland, there is expected to be a huge traffic flow because of people travelling to celebrate with family and friends. For any 1 ≤ i < j ≤ N, there will be exactly one person who wants to go from city i to city j. To achieve this, he should ask Chef or Fehc for VIP cards and travel along the roads permitted by the cards. However, Chef and Fehc are in a competing relationship, and hence any one person can only get one VIP card. A person will choose that company that has a shorter(cheaper) route from city i to city j, buy that company's VIP card, and travel along that company's roads. If there is a tie, he chooses an arbitrary company(this doesn't affect the answer of the problem).
There are M=N*(N-1)/2 people who will travel on New Year's Day. Your task is to compute the total amount of Chefcoins spent by them.
- The first line of input contains a single integer T denoting the number of test cases.
- For each test case, the first line contains a single integer N denoting the number of cities in Chefland.
- The next N-1 lines each contain three space-separated integers ai, bi and ci, denoting a road by Chef's company.
- The next N-1 lines each contain three space-separated integers pi, qi and ri, denoting a road by Fehc's company.
For each test case, output one number denoting the total amount of Chefcoins that will be spent by the M travellers.
- 1 ≤ T ≤ 1000
- 2 ≤ N ≤ 50000
- the sum of N over all test cases ≤ 200000
- 1 ≤ ai, bi, pi, qi ≤ N
- 1 ≤ ci, ri ≤ 4096
Subtask #1 (8 points):
- N ≤ 1000
- the sum of N over all test cases ≤ 5000
Subtask #2 (10 points):
- For any 1 ≤ i < N, ai = pi, bi = qi, ci = ri. In other words, Chef's and Fehc's traffic networks are exactly the same.
Subtask #3 (23 points):
- Fehc's traffic network is a chain 1-2-3-...-N
Subtask #4 (59 points):
- original constraints
Input: 2 3 1 2 3 2 3 2 1 3 2 2 3 3 6 4 3 2 4 5 2 2 4 2 4 6 2 1 5 1 6 3 2 1 5 1 2 4 1 6 5 1 4 6 2 Output: 7 39
Example case 1: There are 3 people:
- The first person goes from city 1 to city 2. He chooses Chef's roads and pays 3 chefcoin.
- The second person goes from city 1 to city 3. He chooses Fehc's roads and pays 2 chefcoin.
- The third person goes from city 2 to city 3. He chooses Chef's roads and pays 2 chefcoin.
|Tags||centroid-decomp, dfs-order, fenwick-tree, hard, lca, ltime52, r_64|
|Time Limit:||9 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.