#P6549. 「2020-2021 集训队作业」不讲武德

    ID: 6028 传统题 1000ms 256MiB 尝试: 4 已通过: 1 难度: 10 上传者: 标签>难度分类NOI/NOI+/CTS数值计算与优化乘积目标参数化线性化贪心拟阵贪心图论Kruskal数据结构Link-Cut Tree离线与分治事件排序计算几何事件同坐标排序有理数精确运算模拟与实现技巧增量维护构造与建模势能分析CF3200

「2020-2021 集训队作业」不讲武德

「2020-2021 集训队作业」不讲武德

题目描述

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

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

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

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

形式化地,对每个 k=1,2,…,n−1k=1,2,\ldots,n-1,从原图选取恰好 kk 条边构成无环边集 SS,最小化

$$\left(\sum_{e\in S}a_e\right)\left(\sum_{e\in S}b_e\right).$$

选出的边不必连通,可以构成森林;孤立点不影响计数。原图允许重边,但同一对顶点间的两条重边不能同时选入无环边集。每个 kk 独立选择最优边集,只需输出最小值。

输入格式

从标准输入读入。第一行一个正整数 TT,表示数据组数。

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

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

输出格式

对于每组数据,向标准输出输出一行 n−1n-1 个数字,第 ii 个数字表示 k=ik=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

数据范围与提示

对于所有数据,保证 $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≤i<j≤m1 \le i < j \le m,都有 ai≠aja_i \neq a_j 或者 bi≠bjb_i \neq b_j,即二元组 (ai,bi)(a_i,b_i) 两两不同。

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

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

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

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

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