#684. 【NFLSPC #3】不讲武德

题目类型:传统型 时间限制:2000 ms 空间限制:512 MiB
输入文件:标准输入 输出文件:标准输出 答案检查器:文本比较

题目描述

题意已更新,数据范围、输入输出格式均有改动,且需要多测

之前的提交由于输入格式关系已经不能通过此题,但是大家的提交记录仍然保留着没有删除

马宝锅老师和一位年轻人准备在一张 $n$ 个点、$m$ 条边的无向图上比武。由于年轻人担心马宝锅老师骂他不讲武德,因此他需要改进一下比赛场地。

对于每条无向边,有两个参数:地板的光滑度 $a_i$ 以及两侧墙的光滑度 $b_i$。年轻人需要选出恰好 $k$ 条边,并删掉剩下所有的边。

为了不让马宝锅老师会方便逃跑,年轻人要求这 $k$ 条边不形成环。此外,为了不让马宝锅老师摔倒来讹他,年轻人要求这 $k$ 条边的 $a_i$ 之和乘以 $b_i$ 之和尽量小。

由于他还没有确定 $k$ 到底是多少,因此你需要对于 $1 \le k < n$ 的所有 $k$ 求出答案。

输入格式

第一行一个正整数 $T$,表示数据组数。

对于每组数据,第一行两个正整数 $n,m$,表示点数和边数。

接下来 $m$ 行每行四个正整数 $a_i,b_i,u_i,v_i$,表示这条边的地板光滑度、墙的光滑度以及连接的两个点。

输出格式

对于每组数据输出一行 $n-1$ 个数字,第 $i$ 个数字表示 $k=i$ 时的答案。

样例输入 1

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

样例输出 1

2 12 40

样例解释

$k=1$ 时,选的边是 $(2,4)$。

$k=2$ 时,选的边是 $(2,4),(3,4)$。

$k=3$ 时,选的边是 $(2,4),(3,4),(1,2)$。

数据范围

对于所有数据,保证 $n-1 \le m \le 1500,\sum m^2 \le 2.5\times10^6,1 \le u_i,v_i \le n,u_i \neq v_i,1 \le a_i,b_i \le 2\times10^6$,输入的图是连通图,并且对于任意的 $1 \le i < j \le m$,都有 $a_i \neq a_j$ 或者 $b_i \neq b_j$,即二元组 $(a_i,b_i)$ 两两不同。

$\text{subtask1(10pts)}:n,m \le 20,T=1$

$\text{subtask2(20pts)}:n-1=m$,即输入的边构成一棵树,且 $n \le 50$

$\text{subtask3(20pts)}:n,m \le 50$

$\text{subtask4(20pts)}:n-1=m$,即输入的边构成一棵树。

$\text{subtask5(30pts)}:$ 无特殊限制。


$by\ \text{wzy}$