Dhaka Regional ACM ICPC 2016 Preleminary Contest Solution D - Double Trouble

D. Double Trouble

Score: 1

CPU: 1s
Memory: 1200MB

Camden is an evil town with N zones and (N - 1) tunnels in between the zones. The newly elected mayor of Camden ensured that every zone is reachable from all the other zones through these tunnels.
You may wonder why it is being called ‘evil’. Well, people say that every zone of Camden offers some level of trouble. Depending on this level, each zone is categorized to be either Minder (less trouble) or Meer (more trouble).
And now say hello to Mr. Milo, who will be moving to Camden very soon, thanks to his new job! He was wiki-ing about Camden while he freaked out as he learned about the extreme risk of getting into trouble in the town he is relocating to. Fortunately, his office is going to be in a Minder zone, and before going to sleep, he decided that by all means he is going to live in a Minder zone as well.
But that night he had a nightmare that even though he was living in a Minder zone, on his direct way to the office from his home, he had to face, not one, but two different Meer zones!
He woke up terrified and tried to distract himself quickly, so instead of freaking out anymore, he began to think in how many ways, he can have a situation where he is living in a Minder zone which has exactly two different Meer zones on the way to the office from itself. But he is too nervous to solve it right now, can you help him?
N.B: Out of extreme anxiety after waking up, Mr. Milo forgot which Minder zone his office is situated in. So, for the problem he made up, he is considering all possible Minder zones as his possible office location.

Input

Input file contains an integer in the first line, number of test cases T (1 ≤ T ≤ 15), and T cases follow. Each case begins with an integerN(1 ≤ N ≤ 100000). The next line contains N space separated integers. The i’th integer is 0 if zone-i is Minder, and the i’th integer is 1 if zone-i is Meer. Then N-1 lines follow, each line have two integers x, y, which denotes there is a tunnel between zone-x and zone-y.

Output

The output file contains case number, followed by the number of ways you can pick two Minder zones so that there are exactly 2 Meer zones on the direct way from one to the other.

Sample

InputOutput
1 5 0 1 1 0 0 1 2 2 3 3 4 4 5 Case 1: 4

Explanation of Sample Test Case:
There can be four possible scenarios for zone selection as (home, office): (1, 4), (1, 5), (4, 1), (5, 1).























Comments

Post a Comment

Popular posts from this blog

Solution - Timus Problem 1293. Eniya

1293. Eniya Time limit: 1.0 second Memory limit: 64 MB It’s restless now on the slips of the intergalactic port’s sixth dock of planet of Torn. No longer then in a month the reconstruction of the small ironclad corvette “Eniya” will be finished. And again this battle ship and its brave team would have to struggle for the control over plutonium mines of Sibelius. The work cannot be stopped even for a second, self-powered laser welders work round the clock. Joints of robots-repairers fuse because of this permanent work. Nevertheless, they can’t stop not for a single moment. Now in all this turmoil it is discovered that corvette’s thermopanels again need an urgent processing with thorium sulphide. It is known that the processing of the one square meter of the panel needs 1 nanogramm of sulphide. In general, it is needed to process  N  rectangular panels, which dimensions are  A  by  B  meters. It is necessary to calculate as fast as possible, how m...
Read more...

Solution - Codeforces Problem 327B - Hungry Sequence

B. Hungry Sequence Iahub and Iahubina went to a date at a luxury restaurant. Everything went fine until paying for the food. Instead of money, the waiter wants Iahub to write a Hungry sequence consisting of  n  integers. A sequence  a 1 ,  a 2 , ...,  a n , consisting of  n  integers, is  Hungry  if and only if: Its elements are in increasing order. That is an inequality  a i  <  a j  holds for any two indices  i ,  j   ( i  <  j ) . For any two indices  i  and  j   ( i  <  j ) ,  a j  must  not  be divisible by  a i . Iahub is in trouble, so he asks you for help. Find a Hungry sequence with  n  elements. Input The input contains a single integer:  n  ( 1 ≤  n  ≤ 10 5 ). Output Output a line that contains  n  space-separated integers  a 1   a 2 , ...,  a n   (1 ≤  a i  ≤ 10 7 ) , representing a ...
Read more...

Solution - Timus Problem 1409. Two Gangsters

1409. Two Gangsters Time limit: 1.0 second Memory limit: 64 MB Two gangsters Harry and Larry had a rest at countryside. They decided to spend some time shooting, so they put several beer cans (no more than 10) on a log. Harry started to shoot cans one after another from the leftmost to the right and Larry – from the rightmost to the left. At some moment it happened so that they shot one and the same can. Harry got indignant and claimed that Larry owed him a considerable sum of money because Larry deprived him of shooting some more cans. Larry became furious and told Harry that he owed even greater sum of money to Larry because of the same reason. They started to argufy but nobody remembered how many cans there were at the very beginning. And no one of them was going to search cans which was shot. Anyway, each of them remembered exactly how many cans he shot. Determine how many cans were not shot by Harry and how many cans were not shot by Larry. Input The only inp...
Read more...