P8630 - Weighted Beautiful Tree

内存限制：128 MB 时间限制：5 S

题面：传统评测方式：文本比较上传者：

提交：1 通过：1

A tree is a connected graph with nodes and edges.

You are given a weighted tree with nodes. The -th node has a weight of $w n_{i}$ and a cost of $c_{i}$ . The -th edge connecting node $u_{i}$ and $v_{i}$ has a weight of $w e_{i}$ . The edge is called beautiful if and only if it meets $min (w n_{u_{i}}, w n_{v_{i}}) \leq w e_{i} \leq max (w n_{u_{i}}, w n_{v_{i}})$ .

You can do the following operation several times.

Choose a node , then change its weight $w n_{u}$ into $w n_{u'}$ . The total cost adds $c_{u} ∣ w n_{u} - w n_{u'} ∣$ .

What is the minimum total cost to make all edges beautiful?

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

For each test case, output an integer in a single line, denoting the minimum total cost.

3
2

2022 杭电多校第七场

8630: Weighted Beautiful Tree

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

分类标签