题意：
给定一个无向连通图，问最少要添加多少条边，可以使得这个图是边双连通的。
题解：
t
a
r
j
a
n
tarjan
tarjan缩点后图变成树，首先特判树中点数
n
≤
2
n\leq 2
n≤2的情况。
考虑
n
>
2
n>2
n>2的情况，以任意一个度大于1的点为根，叶子个数为
g
g
g ，答案为
⌊
g
+
1
2
⌋
\lfloor \frac{g+1}{2} \rfloor
⌊2g+1⌋。
构造具体方案时，以任意度大于
1
1
1的点为根，只需要保证任意两个叶子连边后与根成环，
当奇数个叶子时，可以将一个叶子与根相连，又转换成了偶数叶子情况。
具体构造：
t
a
r
j
a
n
tarjan
tarjan缩点后图变成树，选择度大于
1
1
1的点为根，按照
d
f
s
dfs
dfs序存下所有叶子，
l
e
a
f
[
i
]
leaf[i]
leaf[i]表示
d
f
s
dfs
dfs序的第
i
i
i个叶子，共
g
g
g个叶子。将
l
e
a
f
[
i
]
leaf[i]
leaf[i]与
l
e
a
f
[
i
+
⌊
g
2
⌋
]
leaf[i+\lfloor \frac{g}{2}\rfloor]
leaf[i+⌊2g⌋]连边，
(
i
≤
⌊
g
+
1
2
⌋
)
(i\leq\lfloor \frac{g+1}{2}\rfloor)
(i≤⌊2g+1⌋)。
其实我并没有太理解这个做法的证明，如果有大佬明白可以在评论区解答下~
例题：
2020牛客多校第三场
C
C
C
含有官方题解的博客
upadte:
最近又看了眼这题，简单说下对于这个做法的理解。
首先，这个问题的思路在于使得所有的叶子与根成环，最坏的情况就是每个叶子与根都连一条边。
我们思考什么情况下可以使得这个环的数量变少？
对于奇数个叶子，可以让一个叶子与根连边，问题又转换为了偶数个叶子（选择哪个叶子与根连取决于下面的构造方案，剩下一个没有连边的叶子就是与根直接连边的）。
由于根可以到达每个叶子，考虑叶子之间是否可以连边。
设根为 root ，叶子1为 u ，叶子2为 v。
如果 root->u 和 root->v 两条路径上没有重边，则加上一条边 u-v ，构成了一个环，那么 root, u, v 在的这条环必然是边双连通的。
一个直观的思路是：如果两个叶子处于根的不同子树中，那么这两个叶子就可以连条边。
这种情况下，根到两个叶子的路径是无重边的。
但是对于这种情况呢？
不管怎么样，2 的子树中只有一个叶子与 7 相连，2 的子树中另外两个叶子相连后，其中的点可以借助与 7 相连的叶子构成的环，到达树上其他任何点。
对于 4 和 6 两个叶子来说，虽然未和根成环，但是可以通过走到 5 ，去走 5 所在的环来间接与 根成环。
所以我们可以统计根的每个子树下的点的数量。
假设第 i i i 个子树下的点的叶子的值为 i i i ，目标是使得有尽可能多的数对，数对中的两个数尽可能不同。配对结束后，最多剩下一种数没有配对完。其内部配对一下即可。
但是这里假设是 1 2 3 3 呢，1 和 2 配对，3 和 3配对，这会导致子树 3 任意一个叶子都不能与根成环，所以目标在于使得任意一个子树中都有至少一个点和其他子树中的点相连。当然，如果是 1 2 3 这种情况，1 和 2 配对，子树 3 未与根成环，那么直接将其与根连边即可。
总结来说：有 n 个不同的子树，那么先将 1 和 2 配对，3 和 4 配对，5 和 6 配对…，如果 n 为奇数，最多剩下一个 n 未与其他数配对，如果 1,2,3,…,n-1不止一个，则 n 可以与其中一个数配对，否则 n 直接与根相连。剩下的数随意连即可。
对于构造方案：假设序列为：a = [1, 1, 2, 2, 3, 3, 4]
a[1] 与 a[1 + 7/2] = a[4]
a[2] 与 a[2 + 7/2] = a[5]
a[3] 与 a[3 + 7/2] = a[6]
a[4] 与 a[4 + 7/2] = a[7]
如果说这其中任意两个数都相同，说明这个树的根只有一个子树，这与我们要求的根至少度为 2 矛盾。
否则对于一种数来说，按这种方式必然会和其他种数配对一次。
