8630: Weighted Beautiful Tree

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.

• Choose a node u, then change its weight wnu into wnu′. The total cost adds cu∣wnu−wnu′∣.

The first line contains an integer T, denoting the number of test cases.

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