等了好久才开始学的…

今天看见有个疑似基环树的题就学习了一个

沙茶的 基环树DP不详解

环基树的DP可以用来解决一类$n$个点$n$条边的”树”上的问题

环基树的基本思想就是找到环, 找环上任意一条边$b_i$, 任何断掉他

假设一个点的状态为$0$的时候, 他周围的点的状态可以是$0$也可以是$1$, 我们就从$b_i.from$和$b_i.to$这两个点分别出发 进行树上的DP(这时候已经断掉了一条边, 所以是树上的DP), 比较这两个点的$0$状态的收益大小, 收益大的加进$ans$中

为什么是$0​$状态? 因为我们从$from​$出发的时候并不知道$to​$会是什么状态, 进行DP的时候也不能固定$to​$的状态(而他们之间又有边相连, 他们之间的状态), 只好定一个无论$to​$是什么状态都可以的状态作为初始状态; 以$to​$为起点进行DP的时候亦然

沙茶水过的 丰年好大水题

[ZJOI2008]骑士

就没有上司的舞会, 套一下找环和DP就可以了

沙茶的 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000000 + 5)
#define LL long long
using namespace std;
struct edg
{
    int from, to, next;
}b[MAXN << 1];
int g[MAXN], cntb = -1, cirfrom, cirto, ciredg, n;
bool vis[MAXN];
LL val[MAXN], ans, f[MAXN][2];
void adn(int from, int to)
{
    b[++cntb].next = g[from];
    b[cntb].from = from;
    b[cntb].to = to;
    g[from] = cntb;
}
void cir(int dq, int fe)
{
    vis[dq] = true;
    for (int i = g[dq]; ~i; i = b[i].next)
        if ((i ^ 1) != fe)
        {
            if (vis[b[i].to])
            {
                cirfrom = b[i].from;
                cirto = b[i].to;
                ciredg = i;
            }
            else
                cir(b[i].to, i);
        }
}
void zkj(int dq, int fe)
{
    f[dq][0] = 0, f[dq][1] = val[dq];
    for (int i = g[dq]; ~i; i = b[i].next)
        if ((i ^ 1) != fe && i != ciredg && (i ^ 1) != ciredg)
        {
            zkj(b[i].to, i);
            f[dq][0] += max(f[b[i].to][0], f[b[i].to][1]);
            f[dq][1] += f[b[i].to][0];
        }
}
int main()
{
//    cout << "Hello world!" << endl;
    memset(g, -1, sizeof(g));
    memset(vis, false, sizeof(vis));
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int srx;
        scanf("%lld%d", &val[i], &srx);
        adn(srx, i);
        adn(i, srx);
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i])
        {
            cir(i, -1);
            zkj(cirfrom, -1);
//            LL REfun = max(f[cirfrom][0], f[cirfrom][1]);
            LL REfun = f[cirfrom][0];
            zkj(cirto, -1);
            ans += max(REfun, f[cirto][0]);
//            ans += max(max(f[cirto][0], f[cirto][1]), REfun);
        }
    printf("%lld", ans);
    return 0;
}

/*
3
10 2
20 3
30 1
*/

from 大半年前(2017-10-28 20:39)就AC的守望:

所以可能存在环和多个连通块
联想一道题 城市环路
把环分开
因为两个端点矛盾
所以两个端点分别dfs
累加每个连通块的最大值

太强了Orzzzzzzz

[POI2008]枪战Maf

他们好像都写的贪心…

但是为什么我一眼基环树DP? 挖个坑

By 只会丢人的 Cansult