F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Penguin Love Tour

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 493    Accepted Submission(s): 128


Problem Description
Penguin loves driving. One day he found some islands, and wanted to go on a tour.

These $n$ islands are connected by $n - 1$ undirected roads, the $i$-th road connects island $u_i$, $v_i$ take $w_i$ to pass. Any two islands can reach each other. The i-th island has a power value $p_i$. You can do the following operations at most once for each island:

1. Choose a road that connects to the island

2. Change the cost of the road $w$ to $max(0,w-p)$

The penguin will choose an island arbitrarily and follow the shortest path to another island. Since the penguin likes to travel long distances, he will choose the longest path from all possible options.But you don't want to make his journey too tiring. Can you reasonably allocate the power value of each island to make the penguin's travel as short as possible?
 

Input
The first line contains an integer $T(T \le 1000)$. Then $T$ test cases follow.

For each test case the first line contains one integer $n(1\le n\le 10^5)$.

Then a line with $n$ integers, $p_1, p_2, ..., p_n$ $(0 \le p_i \le 10 ^ 5) $ the power of the islands.

Then $n - 1$ lines, each line containing three integers $u_i$, $v_i$, $w_i$ $ (1 \le u_i, v_i \le n, 1 \le w_i \le 10^5)$ describing a road.

It is guaranteed that $\sum n <4\times10^5 $.
 

Output
For each test case, print a line with an integer, representing the shortest travel length.
 

Sample Input
1 9 3 2 1 1 2 2 4 4 3 5 3 5 4 2 1 6 4 1 2 1 1 3 2 2 9 2 4 7 5 3 8 4 4
 

Sample Output
3
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-29 17:48:59, Gzip enabled