Tree of Candles

2

3 votes
Greedy algorithm, Algorithms, Greedy Algorithms, Trees, Priority queue, Basics of Greedy Algorithms
Problem

This Diwali, El has decided to create a tree-like candle structure. El has N candles numbered from 1 to N arranged in the form of a tree, rooted at candle-1. The ith candle can burn for Ci  minutes and then it vanishes completely.
El now wants to light the candles, but he has some constraints. He can light only one candle a minute and to light a candle, all of its ancestors must have been lit. He wants to know if there exists an order to lit the candles following the above constraints such that all candles are burning simultaneously, if there exists such order, what is the maximum number of minutes all candles can burn simultaneously.
Print only one integer: The maximum number of minutes all candles can burn simultaneously, if it not possible for all candles to burn simultaneously then print 0.

Input Format

  • The first line contains t - the number of test cases.
  • For each test case first line contains N - The number of candles in the tree. 
  • Second line of each test contains N space separated integers C1 to CN - Burning time of each candle.
  • Following N1 line contains 2 space seperated integers x,y denoting that there exists an edge between x and y.  

Constraints

  • 1t1000
  • 1N105
  • 1Ci109 for each i from 1iN
  • The sum of N over all test cases doesn't exceed 5105

Output Format

For each test case print a single integer: The maximum number of minutes all candles can burn simultaneously, if it not possible for all candles to burn simultaneously print 0

Time Limit: 3
Memory Limit: 256
Source Limit:
Explanation

A valid order of burning the candle can be: 1, 4, 3, 5 and then 2.
The life of each candle can be given as:

  • Candle-1: [1, 10]  -   10 minutes
  • Candle-4: [2, 9]    -   8 minutes
  • Candle-3: [3, 17]  -   15 minutes
  • Candle-5: [4, 9]    -   6 minutes
  • Candle-2: [5, 9]   -    5 minutes

The common time all candles are burning is [5,9] which is 5 minutes. It can be shown that this is maximum.

Editor Image

?