6603: Weighted Beautiful Tree
内存限制:128 MB
时间限制:4.000 S
评测方式:文本比较
命题人:
提交:0
解决:0
题目描述
A tree is a connected graph with n nodes and n−1 edges.
You are given a weighted tree with n nodes. The i-th node has a weight of wni and a cost of ci. The i-th edge connecting node ui and vi has a weight of wei. The edge is called beautiful if and only if it meets min(wnui,wnvi)≤wei≤max(wnui,wnvi).
You can do the following operation several times.
You are given a weighted tree with n nodes. The i-th node has a weight of wni and a cost of ci. The i-th edge connecting node ui and vi has a weight of wei. The edge is called beautiful if and only if it meets min(wnui,wnvi)≤wei≤max(wnui,wnvi).
You can do the following operation several times.
- Choose a node u, then change its weight wnu into wn′u. The total cost adds cu|wnu−wn′u|.
输入
The first line contains an integer T, denoting the number of test cases.
For each test case, the input format is as follows:
| n | | | | |
|-----------|-----------|------------|----------|--------|
| c1 | c2 | c3 | … | cn |
| wn1 | wn2 | wn3 | … | wnn |
| u1 | v1 | we1 | | |
| u2 | v2 | we2 | | |
| ⋮ | ⋮ | ⋮ | | |
| un−1 | vn−1 | wen−1 | | |
It is guaranteed that:
For each test case, the input format is as follows:
| n | | | | |
|-----------|-----------|------------|----------|--------|
| c1 | c2 | c3 | … | cn |
| wn1 | wn2 | wn3 | … | wnn |
| u1 | v1 | we1 | | |
| u2 | v2 | we2 | | |
| ⋮ | ⋮ | ⋮ | | |
| un−1 | vn−1 | wen−1 | | |
It is guaranteed that:
- 1≤T≤103
- 1≤n≤105, ∑n≤106
- 1≤ci,wni,wei≤106
输出
For each test case, output an integer in a single line, denoting the minimum total cost.
样例输入 复制
2
3
2 1 2
9 9 10
1 2 10
1 3 11
3
1 1 2
9 9 10
1 2 10
1 3 11
样例输出 复制
3
2