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. ← edited →

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.