Note Tarjan
Part 1 怎么做
自己看书
Part 2 为什么是对的
证明：搜索树是一棵树
由于每个节点都只会访问一次，回溯一次，故会访问(n-1)*2条边，只取访问时的边，即n-1条，可以构成树
证毕。
证明：在一个简单环上的一条边不可能是桥
如果破除这条边，只能把环断成链，不会损坏连通性。
证毕。
证明：桥一定在搜索树上
由上，在一个简单环上的一条边不可能是桥
那么，一个不在搜索树上的一条边，一定与搜索树上的某些边构成简单环。
则它一定不可能是桥。
证毕。
理解：low到底是什么东西？
可以说，low[x]就是从subtree(x)中出发，在只经过一条非树边的情况下，可以到达的最早被访问的点
也就是说:
如果low[x]==dfn[x],就是说subtree(x)只有一条与外界相连的边，即edge(fa(x),x)
如果low[x]<dfn[x],则必然通过非树边可以到达更早访问的节点，他们不在subtree(x)中。
若low[x]>dfn[x],不可能，这不符合定义。
证明：不可能通过一条非树边（x，y)到达dfn[y]>dfn[x]的点y且y不在subtree(x)中
设若可以通过非树边到达满足如上条件的节点y
考虑dfs的遍历过程，可知y一定比x后遍历到，那么有两种情况：
- 是从边（x，y)遍历到y的
- 是从某个x,y的公共祖先遍历而来，即先遍历了x子树，再遍历了y子树
对于第一种情况，则边（x，y)是树边，与假设矛盾。
对于第二种情况，则在遍历x时y尚未遍历，而如果存在边（x，y),就一定会从x到y,那么与假设矛盾；否则，就不存在边（x，y),与假设矛盾。
证毕。
通过如上推理，我们就可以理解为什么需要low数组。并且也给接下来的割边和割点的判定法则的证明提供必要条件。
证明：割点判定法则
由定义可知，如果存在满足条件的节点y，也就是说从subtree(y)中出发只能到达x，不能到达更早的点，由上证明知道，如果不能到达更早的点，则能到达的更晚的点都在subtree(y)中。
那么删除x，剩下的图和subtree(y)就形成了分离的联通块。
然而，如果x为根节点，就有可能不存在“剩下的图”，所以需要至少两个满足的子节点y1，y2。
证毕。
理解：关于重边处理
对于寻找割边的tarjan算法，如果存在重边，则肯定不是割边，换言之，只会有重边中的1条成为搜索树的树边，而其他的必然成环。
对于寻找割点的tarjan算法，由于判定法则可以去等，这意味着即使回到割点x也不影响其成为割点，因为割点的定义就是删除与之相连的所有边。
Part 3 怎么想到这样做
以求割边为例，该问题如果使用暴力解决，则可以枚举树边（如上所证，桥一定是树边），再使用DFS判定连通性。
那么对于tarjan算法，可以拆分成为两个部分：
- 树形DP
- 利用树边判定：
理解方式1： 利用非树边形成环，判定在环上的边不可能是桥（如上证明，环上的边不可能是桥）
理解方式2： 利用非树边返祖（如上证明，利用非树边不可能到达非子树内的非祖先节点），判定子树内有点能返祖的就不是桥
故此优化。
此外，还可以通过树上差分的方式：
- 先按照tarjan的方式进行遍历，当找到一条非树边，就比较两端点的时间戳，按树上差分进行
- 计算子树和，没有被覆盖的边即答案