题目描述

定义基环树为$n$个点、条边且不包含重边和自环的无向连通图。形象化的描述，基环树可以由一棵树再添加一条边后形成(不能是树上已存在的边)现在薯条哥拿到了一个无向图，她想连一条边使得这个无向图变成基环树。

薯条哥想知道，有多少种不同的连边方案?

输入描述

思路

首先添加一条边变成基环树，基环树中恰好有 n 条边，因此初始的 m = n - 1 才可能有合法方案。

之后考虑只能添加一条边，最多只能有两个连通块

• 一个连通块，这个连通块就是一棵树，那么不能连出一条自环，答案就是：$\frac{n\times (n-1)}{2} - (n - 1)$

• 两个连通块，此时两个连通块必然是一棵树和一棵基环树，大小为 $n_1$ 和 $n_2$。那么答案为 $n_1\times n_2$