5085: 不讲武德

内存限制:512 MB 时间限制:3.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:0 通过:0

题目描述

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

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

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

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

输入格式

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

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

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

输出格式

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

输入样例 复制

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

输出样例 复制

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\le1500,\sum m^2\le 2.5\times 10^6,1\le u_i,v_i\le n,u_i \ne v_i,1\le a_i,b_i\le 2\times 10^6$,输入的图是连通图,并且对于任意的$i\le i<j\le m$,都有$a_i \ne a_j$或者$b_i \ne b_j$ ,即二元组$(a_i,b_i)$两两不同。


分值
subtask1 10 $n,m\le20,T=1$
subtask2
20
$n-1=m$,即输入的边构成一棵树,且$n\le 50$
subtask3
20
$n,m\le 50$
subtask4
20
$n-1=m$,即输入的边构成一棵树
subtask5
30