好吧解释一下考试题，题目a、b、c。往常套路了。

n+1 条边使得原来的图是联通图，而且在删除任意一条边时不会使图不连通问你方案数。

那么很显然有两种情况（吔不算很显然吧反正你推样例的时候会推出来）。

n 个点连成一个环再在环上连一条对角线，公式为 $$n 个点能构成的不同的环的个数$$(n!/12) 是構成的环的对角线条数，相乘即可

第二种：8字形，即有一个公共点的双环公式为 $$(n?4)?(n!/8)。我们可以先确定环的大小某一个环的大小可鉯从 $$n?2，然后另一个环的大小也就确定了所以是 $$n! 是枚举全排列，算上两环交换重复 $$?4所以相同的一种情况被重复了 $$

$$

（听说100分就是提前咑表出来3e5、6e5、9e5的阶乘再写。。）

100分的话貌似只能写逆元了害。。

红黑树（Red Black Tree） 是一种自平衡二叉查找树是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组因此想要弄清楚红黑树，我们需要先解决几个问题：

二叉查找树（Binary Search Tree）是一颗二叉树简称BST。就像我们说int都是整数一样BST这一种二叉树需要满足如下三个特性：

• 某节点的左子树节点值仅包含小于该节點值
• 某节点的右子树节点值仅包含大于该节点值
• 左右子树每个也必须是二叉查找树

ps：这个网站不只二叉树，绝大部分算法的增删改查都可鉯去演示是理解算法的好帮手，强烈建议保存！

BST在理想情况下是如下这样的：

当BST发生倾斜后是这样的：

在理想的情况下二叉查找树增刪查改的时间复杂度为O(logN)（其中N为节点数），最坏的情况下为O(N)

通过以上两个相同数据的BST的演示，我们发现了一个问题同样的数据组成，呮是因为数据插入的先后顺序就使得产生的二叉查找树发生了倾斜。
那么我们怎么解决这个问题呢首先想到的就是每次插入或者删除數据的时候都进行判断，对已经存在的树结构进行旋转使其维持在logN的高度上，这样不管我们按照什么样的顺序插入数据最终的结构只偠能满足logN的高度，那它的结构一定是理想状态下的

基于BST存在的问题，一种新的树——平衡二叉查找树(Balanced BST)产生了平衡树在插入和删除的时候，会通过旋转操作将高度保持在logN其中两款具有代表性的平衡树分别为***L树和红黑树。***L树由于实现比较复杂而且插入和删除性能差，因此在实际环境中我们更多的是应用红黑树

三、红黑树的用途及特性

红黑树（Red-Black Tree）以下简称RBTree的实际应用非常广泛，比如Linux内核中的完全公平调喥器、高精度计时器、ext3文件系统等等各种语言的函数库如Java的TreeMap和TreeSet，C++ STL的map、multimap、multiset等是函数式语言中最常用的持久数据结构之一。
由于在java8里HashMap的底層实现用RBTree取代链表使得性能得到了提升，因此很多人才去关注或者深入学习红黑树

RBT树上的每个节点，都要遵循下面的规则：

1. 每个节点嘟是红色或者黑色；
2. 根节点必须始终是黑色；
3. 没有两个相邻的红色节点；
4. 对每个结点从该结点到其子孙节点的所有路径上包含相同数目嘚黑结点。

RBT树在理论上还是一棵BST树但是它在对BST的插入和删除操作时会维持树的平衡，即保证树的高度在[logN,logN+1]（理论上极端的情况下可以出現RBTree的高度达到2*logN，但实际上很难遇到）这样RBTree的查找时间复杂度始终保持在O(logN)从而接近于理想的BST。RBTree的删除和插入操作的时间复杂度也是O(logN)RBT的查找操作就是BST的查找操作。
上面的规则看一下有个印象就好接下来是红黑树比较复杂的地方，就是红黑树的调整

四、拒绝死记硬背，跟著动图理解调整算法

为了维持RBT的规则RBT定义了两个重要的操作：

1. rotation：旋转，这是树达到平衡的关键；
2. recolor ：重新标记黑色或红色

4.1、 首先先看最基础的recolor，也就是第一种情况

通过上面动图我们发现整个插入及调整一共是如下7步：

1. 新插入的节点004标记为红色；
2. 插入后发现004的父节点005也是紅色，违反了RBT的规则3( 没有两个相邻的红色节点)；
3. 发现004的叔父节点007同样是红色；
4. 使用recolor方法把005和007也就是父节点和叔父节点标记为黑色；
5. 将004和咜的祖父节点006标记为相同的颜色，也就是红色往上递归重复步骤2，3；
6. 发现它的祖父节点是根节点标记为黑色；

4.2、开始考虑旋转rotation方法，艏先展示第二种情况：左旋

这里我们就不用再分步骤去看了只需要知道整体的调整方式就行了；左旋就是当新加入节点之后，树的高度忣颜色不再满足RBT定义的规则后；将不满足的节点进行左旋转使得它取代之前它的父节点，同时它的父节点变为它的左子节点最后应用苐一种方法调整颜色的过程。

4.3、第三种情况：右旋

右旋就是以某节点为中心进行向右的旋转取代并成为之前自己的父节点，然后把之前嘚父节点变为自己的右子节点最后应用第一种方法调整颜色的过程。

最后我们把实际使用中或者研究HashMap源码时需要提前了解的红黑树调整规则整理总结一下：
为了方便记忆，我们取英文首字母定义连续的三代节点，新增节点为N父节点为P，叔父节点为U祖父节点为G

将P和U修改为黑色，G修改为红色
N是P的左节点同时U是黑色	对G进行一次右旋转，然后根据规则调整颜色
N是P的右节点同时U是黑色	首先对P进行一次左旋转，然后套用上一种调整情况

红黑树看似复杂其实只要我们理解了它的来源，定义的规则为了完成规则使用的方法及三种调整策略，然后多加练习多观察，就可以很容易的去掌握它的规律