Woburn Challenge 2017-18 Finals Round - Senior Division

Problem 3: Explosive Ordinance Disposal

The Party of Extraterrestrial Gangsters has begun its invasion of Earth! Vast armies of PEG soldiers have been deployed down to the surface throughout Scarberia, and the cows and monkeys have engaged them in battle.

Amidst the fighting, however, the aliens have also transported something else to the planet's surface — a bomb with devastating nuclear power! All life in Scarberia, and perhaps the rest of Earth, would surely cease if the bomb were to detonate. Fortunately, the PEG leaders are honourable enough to give their enemies a fighting chance. As such, they've set the bomb to go off after a period of three hours, and implanted a system for defusing it. They've even included an instruction manual along with it!

On the surface of the bomb, there are N (1 ≤ N ≤ 200) electrical terminals. There are also N − 1 wires running amongst the terminals, the i-th of which runs between terminals A_i and B_i (1 ≤ A_i, B_i ≤ N), and is either black (if C_i = 0), or is otherwise white (if C_i = 1). The wires have been arranged such that all pairs of terminals are reachable from one another by following a sequence of wires.

Bo Vine and the Head-Monkey have gotten their hands on the bomb and its accompanying instruction manual. According to the manual, the bomb will turn itself off if the following conditions are all met:

1. Each terminal i receives an electrical current with some voltage V_i, such that V_i is a positive integer.
2. For each black wire i (such that C_i = 0), the greatest common divisor (GCD) of V_Ai and V_Bi is equal to 1.
3. For each white wire i (such that C_i = 1), the GCD of V_Ai and V_Bi is greater than 1.

Bo Vine has ordered his cow engineers to prepare the necessary electrical equipment as quickly as possible. Meanwhile, the Head-Monkey has personally taken it upon herself to come up with a set of voltages V_1..N which will successfully satisfy the conditions to defuse the bomb. However, having realized that PEG is essentially mocking them by dispatching a bomb which may be defused so easily, she's decided to get back at them by demonstrating the monkeys' superior intelligence and successfully defusing the bomb using as little voltage as possible. Help the Head-Monkey determine the minimum possible total voltage (sum of V_1..N values) required to get the job done. Just make sure to figure it out within three hours!

Subtasks

In test cases worth 3/17 of the points, C₁ = C₂ = … = C_{N − 1}.

Input Format

The first line of input consists of a single integer, N.
N − 1 lines follow, the i-th of which consists of three space-separated integers, A_i, B_i, and C_i, for i = 1..(N − 1).

Output Format

Output a single integer, the minimum possible total voltage required to defuse the bomb.

Sample Input

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

Sample Output

16

Sample Explanation

It's optimal to send

• a 1-volt current to terminal 5;
• 2-volt currents to terminals 1, 2, and 4; and
• 3-volt currents to terminals 3, 6, and 7.

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 4.00s
Memory Limit: 64M
Added: May 13, 2018
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

This problem has been altered from the version used in the live Woburn Challenge Finals, to eliminate possible uncertainty regarding the strength of test data for the original version. In particular, the bound on N has been reduced from 200,000 to 200, new test data has been generated, and all submissions have been rejudged for this version. We apologize for the issue!

The official "solution" on https://woburnchallenge.com/past-contests/ does not reflect the change. I think you should update the PDF to warn about the incorrect solution.

Thanks, we'll get that updated shortly!