基环树

一.首先定义看定义

树是N个点N-1条边的联通图

基环树是N个点N条边的连通图

不保证联通就都是森林

所以基环树就是在树上加了一条边，使得树上有了一个环
基环树的常见处理方法

1. 把环上的一条边单独处理， 这样其余部分依然是一棵树
2. 把环单独处理， （缩成一个点）这样其余部分依然是一棵树

二、内向树和外向树 (有向)

所谓内向树的定义是每个点有且只有一条出边。也就是这棵树给人的大体感觉是向内的。
所谓外向树的定义是每个点有且只有一条入边。也就是这棵树给人的大题感觉是外向的。

基环内向森林 找最小环link

基环内向树有一个性质就是，从连通块内任意一点出发，一定可以走到环内。
为什么vis不开bool是因为要保证找到的环是当前这一轮找到的，如果是只是上一轮已经走过了的就不用管。不然复杂度炸了

    rep(i, 1, n) cin >> to[i];
    int ans = 1e9;
    rep(i, 1, n) if(! vis[i])
    {
        int k = i;
        while(! vis[k]) vis[k] = i, k = to[k];
        if(vis[k] == i)
        {
            int t = k, res = 0;
            while(to[t] != k) t = to[t], res ++;
            ans = min(res + 1, ans);
        }
    }
    cout << ans;

拆环 link

显然是基环树，用并查集先找到环，然后随意找一条边 A -> B，把这条边断开，剩下的树形dp即可
A 选 B 不选
A 不选 B 选
A 不选 B 不选
但是要注意分讨一下

	if(u == A || u == B)
	{
		if(op == 1) // 选A, 不选B 
			if(u == A) f[u][0] = inf;
			else f[u][1] = inf;
		else if(op == 2) // 不选A, 选B 
			if(u == A) f[u][1] = inf;
			else f[u][0] = inf;
		else // 都不选
			f[u][1] = inf;
	}

要满足A, B不能同时选，所以正常转移后要判断一下

还有一个方法是把环单独处理，先对环外的树形结构都dp一下求出答案，再考虑合并