BZOJ 1040: [ZJOI2008]骑士 | 在基环外向树上DP

题目:

http://www.lydsy.com/JudgeOnline/problem.php?id=1040

---

题解:

考虑断一条边

这样如果根节点不选答案一定正确

但是如果选了的话有可能他爸爸也选了

所以我们强制他爸爸选再更新答案

按照以上思路,存图存单向边即可

#include<cstdio>

#include<algorithm>

#include<cstring>

#define N 1000005

using namespace std;

typedef long long ll;

int n,val[N],fa[N],cnt[N],head[N],tot,ecnt;

bool vis[N];

ll ans,f[N][];

struct edge

{

    int nxt,v;

}e[N];

inline void add(int u,int v)

{

    e[++ecnt].v=v;e[ecnt].nxt=head[u]; head[u]=ecnt;fa[v]=u;

}

inline void Dfs(int x)

{

    int y;vis[x]=;f[x][]=val[x];

    for (int i=head[x];i;i=e[i].nxt)

    if (!vis[y=e[i].v])

    {

        Dfs(y);

        f[x][]+=max(f[y][],f[y][]);

        f[x][]+=f[y][];

    }

}

inline void Dp(int x)

{

    int rt,y;

    for (rt=x;cnt[rt]!=x;rt=fa[rt])

    cnt[rt]=x;

    Dfs(rt);

    x=fa[rt];

    f[x][]=f[x][];

    for (x=fa[x];x!=rt;x=fa[x])

    {

    f[x][]=;f[x][]=val[x];

    for (int i=head[x];i,y=e[i].v;i=e[i].nxt)

        f[x][]+=max(f[y][],f[y][]),f[x][]+=f[y][];

    }

    f[rt][]=val[rt];

    for (int i=head[rt];i;i=e[i].nxt)

    f[rt][]+=f[y=e[i].v][];

    ans+=max(f[rt][],f[rt][]);

}

int main()

{

    scanf("%d",&n);

    for (int i=,u;i<=n;i++)

    {

    scanf("%d%d",&val[i],&u);

    add(u,i);

    }

    for (int i=;i<=n;i++)

    if (!vis[i]) Dp(i);

    printf("%lld\n",ans);

    return ;

}