Maximum Deviation Spanning Tree

View as PDF

Submit solution

All submissions

Best submissions

Points: 25 (partial)

Time limit: 2.0s

Memory limit: 512M

Problem type

Given a sequence $A = [a_1, a_2, \ldots, a_n]$ ~A = [a_1, a_2, \ldots, a_n]~, the deviation of the sequence is defined as the minimal value of $\sum_{i}{|a_i - x|}$ ~\sum_{i}{|a_i - x|}~, where $x$ ~x~ can be any real number. For example, the deviation of $[2, 1, 4]$ ~[2, 1, 4]~ is $3$ ~3~, which can be achieved when we choose $x=2$ ~x=2~.

Similarly, given a tree, the tree's deviation is defined as the deviation of the tree's edge weight sequence. Now, given a connected graph, please write a program to find a spanning tree with the maximal deviation.

Note, there may be multiple edges between the same pair of vertices.

Input Specification

The first line of input contains two integers, $N$ ~N~ and $M$ ~M~ ( $2 \le N \le 2 \times 10^5$ ~2 \le N \le 2 \times 10^5~, $1 \le M \le 5 \times 10^5$ ~1 \le M \le 5 \times 10^5~), indicating the number of vertices and the number of edges in the given graph.

Each of the following $M$ ~M~ lines contains three integers $u_i$ ~u_i~, $v_i$ ~v_i~ and $w_i$ ~w_i~ ( $1\le u_i, v_i \le N$ ~1\le u_i, v_i \le N~, $1 \le w_i \le 10^9$ ~1 \le w_i \le 10^9~), indicating an undirected edge between $u_i$ ~u_i~ and $v_i$ ~v_i~ with a cost of $w_i$ ~w_i~.

Output Specification

Output one integer, the max deviation of the spanning tree.

Constraints

Subtask	Points	Additional constraints
$1$ ~1~	$15$ ~15~	$N \le 10$ ~N \le 10~, $M \le 20$ ~M \le 20~, $w_i \le 100$ ~w_i \le 100~.
$2$ ~2~	$15$ ~15~	$N \le 100$ ~N \le 100~, $M \le 100$ ~M \le 100~, $w_i \le 100$ ~w_i \le 100~.
$3$ ~3~	$20$ ~20~	$N, M \le 1\,000$ ~N, M \le 1\,000~.
$4$ ~4~	$10$ ~10~	$N, M \le 10^5$ ~N, M \le 10^5~, and $N = M$ ~N = M~.
$5$ ~5~	$15$ ~15~	$N, M \le 10^5$ ~N, M \le 10^5~, and $N$ ~N~ is an odd number.
$6$ ~6~	$25$ ~25~	No additional constraints.

Sample Input

Sample Output

Explanation

A possible spanning tree with the max deviation is to choose the $1$ ~1~st, $3$ ~3~rd, and $6$ ~6~th edges.

Comments

0

maxcruickshanks commented on Dec. 15, 2024, 7:01 p.m. ← edit 3 →

Since the original data were weak, an additional test case was added to subtask 3, and all submissions were rejudged. The issue was noticed by BalintR, and data were provided by maxcruickshanks.