Tree Counting

发布时间: 2018年8月14日 17:33   最后更新: 2018年8月14日 17:37   时间限制: 1000ms   内存限制: 256M

给你一个$n$个顶点的无向完全图$G$,顶点编号为$1 \sim n$以及一个集合$S$。集合$S$中包含图$G$的$n-3$条边。

现在我们要求图$G$的生成树,使该生成树包含这$n-3$条边,问满足条件的不同生成树有多少棵?两棵生成树认为是不同的生成树当且仅当至少有一条边不同。

第一行是一个整数$T$,表示测试数据的组数。 对于每组测试数据:
第一行是一个整数$n$,表示点的数量。
接下来$n-3$行,每行两个整数$u,v$,表示集合中存在边$(u, v)$。
保证没有重边和自环。
$T \leq 20$
$4 \le n \le 1000$
$1 \le u, v \le n$

对于每组测试数据,在一行内输出一个整数表示满足条件的生成树个数。

复制
2
4
1 2
5
1 2
2 3
8
15

对于第一组样例,经过边$\lbrace 1,2 \rbrace$的生成树一共有$8$组,分别是:

$\lbrace (1, 2), (1, 3), (1, 4) \rbrace$

$\lbrace (1, 2), (1, 3), (2, 4) \rbrace$

$\lbrace (1, 2), (1, 3), (3, 4) \rbrace$

$\lbrace (1, 2), (2, 3), (2, 4) \rbrace$

$\lbrace (1, 2), (1, 4), (2, 3) \rbrace$

$\lbrace (1, 2), (1, 4), (3, 4) \rbrace$

$\lbrace (1, 2), (2, 3), (3, 4) \rbrace$

$\lbrace (1, 2), (2, 4), (3, 4) \rbrace$

data structure

ACM集训队暑期集训新生组队赛