Maximum Deviation Spanning Tree

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

Given a sequence 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|}, where x can be any real number. For example, the deviation of [2, 1, 4] is 3, which can be achieved when we choose 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 and M (2 \le N \le 2 \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 lines contains three integers u_i, v_i and w_i (1\le u_i, v_i \le N, 1 \le w_i \le 10^9), indicating an undirected edge between u_i and v_i with a cost of w_i.

Output Specification

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


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

Sample Input

4 6
1 2 1
1 3 2
2 3 5
3 2 4
2 4 3
3 4 2

Sample Output



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


There are no comments at the moment.