【一本通1489：构造完全图】题解

题目链接

题目

对于完全图 \(G\)，若有且仅有一棵最小生成树为 \(T\)，则称完全图 \(G\) 是树 \(T\) 扩展出的。

给你一棵树 \(T\)，找出 \(T\) 能扩展出的边权和最小的完全图 \(G\)。

思路

要使一个图总存在唯一最小生成树，需满足所有非最小生成树的边（假设连接 \(u,v\)），使这条边的边权 \(w\) 大于 \(u,v\) 在最小生成树上的最短路径的最大边权。

因此，我们可以先dfs一遍求出每个点到根节点的最大值，然后完全图上每条边暴力匹配，复杂度是 \(O(n^2)\) 的。

考虑利用类似kruskal的思想，先对最小生成树上的边从小到大排序，然后按排序后的顺序进行操作。

此时对于当前这条边来说，假设其连接 \(x,y\)，且其边权为 \(w\)，如下图所示：

图中橙色边代表新加入的边，\(A,B\) 分别代表与 \(x,y\) 直接或间接相连的节点群，我们可以用并查集把它们并到一个集合里面。

在并查集的过程中，我们记录 \(g_x\) 代表 \(x\) 所在集合的大小，必须满足 \(x\) 是这个集合的祖先。

设 \(x\) 的祖先为 \(u\)，\(y\) 的祖先为 \(v\)。

而我们现在要还原成完全图 \(T\)，则我们在两个集合中任意点都应加边，所以总加边数为 \(g_x\times g_y-1\)。

而由于我们已经排了序，所以 \(w\) 必然是当前树上最大边权，则 \(g_x\times g_y-1\) 条边的边权应为 \(w+1\)。

此时对于树上这条边对答案的贡献为 \((w+1)\times (g_x\times g_y-1)\)。

时间复杂度 \(O(n\log n)\)

Code

// Problem: 1489：构造完全图
// Contest: SSOIER
// URL: http://ybt.ssoier.cn:8088/problem_show.php?pid=1489
// Memory Limit: 65 MB
// Time Limit: 1000 ms

#include
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define N 100010
//#define M
//#define mo
struct node
{
	int u, v, w; 
}a[N]; 
int n, m, i, j, k, T; 
int f[N], g[N], ans, x, y; 

int fa(int x)
{
	if(f[x]==x) return x; 
	return f[x]=fa(f[x]); 
}

bool cmp(node x, node y)
{
	return x.w