圆方树学习笔记

前言

既然老师讲课都讲过了，那还是要学的，本篇文章介绍的圆方树为狭义的圆方树，解决仙人掌上的系列问题。

仙人掌

仙人掌，每条边至多属于一个简单环的连通无向图。

图中没有自环，但是有可能有重边。

圆方树

圆方树做的事情就是把仙人掌的每个环拿出来，建一个新的方点，环的起点向方点连边，方点再向环上其他点连边，原先非环边保留。注意这里点边都只从父亲连向孩子。
上面那个仙人掌建出的圆方树就是这样的

罗马数字的点为方点。

建树

通过tarjan一边求点双一边连边。
tarjan没有什么不同，建树的部分请结合代码和注释理解。

cnt=n;
void tarjan(int u,int fa){//由于有重边，fa存边的编号
    dfn[u]=low[u]=++tim;
    stk[++top]=u;
    for (int p=head[u];p;p=nxt[p]){
        if (p!=fa){
            int v=tow[p];
            if (!dfn[v]){
                tarjan(v,p^1);
                low[u]=min(low[u],low[v]);
                if (dfn[v]==low[v]) s[u].push_back(v);//如果v不在我这个环内，直接连边
            }
            else if (dfn[v]<dfn[u]){//显然整个环中，环的起点dfn最小，所以v即为环的起点
                low[u]=min(low[u],dfn[v]);
                s[v].push_back(++cnt);//建方点
                for (int j=top;stk[j]!=v;j--) s[cnt].push_back(stk[j]);
            }
        }
    }
    top--;
}

这样就把圆方树给建出来了，剩下我们要做的就是根据题目的要求，在圆方树上树形dp就行了。