csp7连测day7T3

如果边权 $k$​ 在最小生成树中，那么这条边的位置已经在树上被确定了。
如果边权 $k$​ 不在最小生成树中，那么这条边的两个端点此时必然属于同一个连通块 Ci，所以
这条边的方案数就是 $\sum E(C_i)$​，其中 $E(C_i)$​ 表示连通块 $C_i$​​​​ 中还有多少对点之间没有边，而这就等
于 $\cfrac{C_i \times (C_i −1)}{2} −E′(Ci)$​​，其中 E′(Ci) 是连通块 Ci 中已经连的边数，而我们之前总共连了 $k − 1$
条边，所以这条边的总方案数就是

$(\sum{\frac{C_i\times (C_i - 1)}{2}}) - k + 1$

根据乘法原理，方案数就是每条边的方案数乘积，而构造方案只需要动态维护当前在同一连通
块 $C_i$ 中的还未添加的边，每次从中任选一条作为边权为 k 的边。
考虑如何维护这些边，不难想到用并查集维护连通性，合并两个连通块时将从两边各选一个点
形成的边加入候选集合即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 2010, P = 1e9 + 7;
struct Edge
{
	int x, y, z;
	bool operator<(Edge b)
	{
		return z < b.z;
	}
} e[N];
int n, ans, cur, ok, f[N], d[N][N];
vector<int> v[N];
queue<pair<int, int>> q;
int findr(int x) { return (f[x] == x ? x : f[x] = findr(f[x])); }
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n - 1; i++)
		scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].z);

	for (int i = 1; i <= n; i++)
		f[i] = i, v[i].push_back(i);
	sort(e + 1, e + n);
	ans = ok = cur = 1;
	for (int i = 1; i <= n * (n - 1) / 2; i++)
	{
		if (cur <= n - 1 && e[cur].z == i)
		{
			d[e[cur].x][e[cur].y] = d[e[cur].y][e[cur].x] = i;
			int fx = findr(e[cur].x), fy = findr(e[cur].y);
			f[fx] = fy;
			int lenx = v[fx].size(), leny = v[fy].size();
			for (int i = 0; i < lenx; i++)
			{
				for (int j = 0; j < leny; j++)
				{
					if (v[fx][i] != e[cur].x || v[fy][j] != e[cur].y)
						q.push(make_pair(v[fx][i], v[fy][j]));
				}
			}
			for (int i = 0; i < lenx; i++)
				v[fy].push_back(v[fx][i]);
			cur++;
		}
		else
		{
			if (q.empty())
			{
				ans = ok = 0;
				break;
			}
			ans = (1ll * ans * (long long)(q.size())) % P;
			d[q.front().first][q.front().second] =
				d[q.front().second][q.front().first] = i;
			q.pop();
		}
	}
	printf("%d\n", ans);
	if (ok)
	{
		for(int i = 1; i <= n; i++,puts(""))
			for(int j = 1; j <= n; j++)
				printf("%d ", d[i][j]);
	}
	return 0;
}