hdu5834 Magic boy Bi Luo with his excited tree（树形dp）

发布时间：2021-01-26 05:28:43 所属栏目：大数据来源：网络整理

导读：Magic boy Bi Luo with his excited tree Time Limit: 8000/4000 MS (Java/Others)????Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 723????Accepted Submission(s): 192 Problem Description ? Bi Luo is a magic boy,he also has a

副标题[/!--empirenews.page--]

Magic boy Bi Luo with his excited tree

Time Limit: 8000/4000 MS (Java/Others)????Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 723????Accepted Submission(s): 192

Problem Description

Bi Luo is a magic boy,he also has a migic tree,the tree has ? N ?nodes,in each node,there is a treasure,it's value is ? V[i] ,and for each edge,there is a cost ? C[i] ,which means every time you pass the edge ? i ?,you need to pay ? C[i] .

You may attention that every ? V[i] ?can be taken only once,but for some ? C[i] ?,you may cost severial times.

Now,Bi Luo define ? ans[i] ?as the most value can Bi Luo gets if Bi Luo starts at node ? i .

Bi Luo is also an excited boy,now he wants to know every ? ans[i] ,can you help him? ?

Input

First line is a positive integer ? T(T≤104) ?,represents there are ? T ?test cases.

Four each test：

The first line contain an integer ? N (N≤105) .

The next line contains ? N ?integers ? V[i] ,which means the treasure’s value of node ? i(1≤V[i]≤104) .

For the next ? N?1 ?lines,each contains three integers ? u,v,c ?,which means node ? u ?and node ? v ?are connected by an edge,it's cost is ? c(1≤c≤104) .

You can assume that the sum of ? N ?will not exceed ? 106 . ?

Output

（编辑：核心网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

1/5

尾页

2022年制造业七大趋向	大数据转型方式首推数
孩子的工程思维计算思	重建通天塔 Meta策划建