「学习笔记」基环树

$Find\;the\;Loop$

该代码可以找二元环。

$code\;by\;$$Gion$

vector<int> G[MAXN]; //基环树

int fa[MAXN];        //dfs时的父亲
int dfn[MAXN], idx;  //访问的时间
int loop[MAXN], cnt; //环

void get_loop(int u) {
    dfn[u] = ++ idx;
    for (int i = 0; i < G[u].size(); i ++) {
        int v = G[u][i];
        if(v == fa[u]) continue ;
        if(dfn[v]) {//v在环上
            if(dfn[v] < dfn[u]) continue ;//v已经被统计了
            loop[++ cnt] = v;//环在u的子树上
            for ( ; v != u; v = fa[v])
                loop[++ cnt] = fa[v];
        } else fa[v] = u, get_loop(v);
    }
}

$Examples$

[ZJOI 2008]骑士

$Description$

基环树版「没有上司的舞会」。

$Solution$

给出两种做法。

问题要求求解的是一个基环树森林。但由于可能存在重边，森林中可能存在树，应该是要考虑进去的。

先以没有上司的舞会的方式处理环的子树($f[i][0/1]$)，再处理环。

由于第一个点和最后一个点不能都选，所以在统计答案时要多加一维，表示1号点选不选。

$g[i][0/1][0/1]$表示环上的第i个点，1号点和i号点是否选择时，得到的最优答案。

再以没有上司的舞会的方式处理就可以了。

$Warning:$可以看出$g[2][1][1]$和$g[1][1][0]$之类是不存在的状态，因此要用到它的状态都要预处理好（$g[1-3]$）。

dfs找出环上的任意两个点$u,v$，强行断开$(u,v)$。由于可能存在重边，要暴力特判。

以它们为根各做一次树形dp，答案取$max(f[u][0],f[v][0])$

两种做法的本质都是断边，但第二种实现较为容易。

~~给出第一种的$90pts$代码。~~

#include<cstdio>
#include<cstring>
#define ll long long

const int MAXN = 1e6 + 10;
int idx = 0, tot = 0, cnt = 0, N;
int Loop[MAXN], dfn[MAXN] = {0}, h[MAXN], fa[MAXN], val[MAXN];
ll g[MAXN][2][2], f[MAXN][2] = {0};
ll Ans = 0;
struct E{
    int t, nxt;
}Ed[MAXN << 1];

ll max(ll x, ll y){return x > y ? x : y;}

int readint()
{
    int ret = 0; char ch = getchar();
    while (ch > '9' || ch < '0') ch = getchar();
    for (; ch <= '9' && ch >= '0'; ch = getchar()) ret = ret * 10 + ch - 48;
    return ret;
}

void Get_Loop(int u)
{
    dfn[u] = ++idx;
    for (int i = h[u]; i; i = Ed[i].nxt)
    {
        int v = Ed[i].t; if (v == fa[u]) continue;
        if (dfn[v])
        {
            if (dfn[v] < dfn[u]) continue;
            Loop[++tot] = v;
            for (; v != u; v = fa[v]) Loop[++tot] = fa[v];
        }
        else {fa[v] = u; Get_Loop(v);}
    }
}

void dfs(int u, int fa)
{
    f[u][1] = (ll)val[u];
    for (int i = h[u]; i; i = Ed[i].nxt)
    {
        int v = Ed[i].t; if (v == fa) continue; dfs(v, u);
        f[u][0] += max(f[v][0], f[v][1]);
        f[u][1] += f[v][0];
    }
}

void Get_F(int u)
{
    f[Loop[u]][1] = (ll)val[Loop[u]];
    for (int i = h[Loop[u]]; i; i = Ed[i].nxt)
    {
        int v = Ed[i].t; if (v == Loop[u - 1] || v == Loop[u + 1]) continue; dfs(v, Loop[u]); 
        f[Loop[u]][0] += max(f[v][0], f[v][1]);
        f[Loop[u]][1] += f[v][0]; 
    }
}

void Dp()
{
    memset(g, 0, sizeof(g));
    Loop[0] = Loop[tot]; Loop[tot + 1] = Loop[1];
    Get_F(1), Get_F(2), Get_F(3);
    for (int i = 0; i <= 1; i++)
        for (int j = 0; j <= 1; j++)
            g[2][i][j] = f[Loop[1]][i] + f[Loop[2]][j];
    g[2][1][1] = 0;
    g[3][0][0] = max(g[2][0][1], g[2][0][0]) + f[Loop[3]][0];
    g[3][0][1] = g[2][0][0] + f[Loop[3]][1];
    g[3][1][0] = g[2][1][0] + f[Loop[3]][0];
    g[3][1][1] = g[2][1][0] + f[Loop[3]][1];
    for (int u = 4; u <= tot; u++)
    {
        Get_F(u);
        for (int i = 0; i <= 1; i++)
        {
            g[u][i][0] = max(g[u - 1][i][0], g[u - 1][i][1]) + f[Loop[u]][0];
            g[u][i][1] = g[u - 1][i][0] + f[Loop[u]][1];
        }
    }
    Ans += max(g[tot][0][0], max(g[tot][0][1], g[tot][1][0]));
}

void AddEdge(int f, int t)
{
    Ed[++cnt].t = t, Ed[cnt].nxt = h[f]; h[f] = cnt;
    Ed[++cnt].t = f, Ed[cnt].nxt = h[t]; h[t] = cnt;
}

int main()
{
    freopen("Brienne.in", "r", stdin);
    N = readint();
    for (int i = 1; i <= N; i++) {val[i] = readint(); int t = readint(); AddEdge(i, t);} 
    for (int i = 1; i <= N; i++)
        if (!dfn[i])
        {
            memset(Loop, 0, sizeof(Loop));
            tot = 0; fa[i] = -1;
            Get_Loop(i); 
            if (!tot) {dfs(i, -1); Ans += max(f[i][0], f[i][1]);}
            else Dp();
        }
    printf("%lld", Ans);
    return 0;
}

$Recommend$

$Find\;the\;Loop$

$Examples$

[ZJOI 2008]骑士

$Description$

$Solution$