【BZOJ1040】骑士

    带一个环的树，把环上两个相邻的点u,v之间的一条边切掉（有两条就只切一条），考虑取u不取v，不取u随意取不取v两种状态，然后做树形dp。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=1000010;
 
int head[maxn],next[maxn<<1],E[maxn<<1],Ecnt;
int v[maxn];
int n;
 
void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}
void Add_Edge(int x,int y) {next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;next[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;}
 
int vis[maxn];
int FindC;
int pu,pv,pe,cu;
LL f[maxn][2];
LL ans;
 
void Find_Circle(int x,int qe)
{
    vis[x]=1;
    for (int i=head[x];i;i=next[i]) if (i!=(qe^1))
        if (vis[E[i]])
        {
            FindC=1;
            pu=x;pv=E[i];
            pe=i;
            return;
        }
        else
        {
            Find_Circle(E[i],i);
            if (FindC==1) return;
        }
}
 
void DFS(int x,int fa)
{
    vis[x]=1;
    if (x!=pu) f[x][0]=f[x][1]=0;
    if (x==pu)
    {
        if (cu==1) f[x][1]=v[x];
        for (int i=head[x];i;i=next[i]) if (E[i]!=fa && (i>>1)!=(pe>>1))
        {
            DFS(E[i],x);
            if (cu==0) f[x][0]+=max(f[E[i]][0],f[E[i]][1]);
            if (cu==1) f[x][1]+=f[E[i]][0];
        }
        return;
    }
    if (x==pv)
    {
        if (cu==0) f[x][1]=v[x];
        for (int i=head[x];i;i=next[i]) if (E[i]!=fa && (i>>1)!=(pe>>1))
        {
            DFS(E[i],x);
            f[x][0]+=max(f[E[i]][0],f[E[i]][1]);
            if (cu==0) f[x][1]+=f[E[i]][0];
        }
        return;
    }
    f[x][1]=v[x];
    for (int i=head[x];i;i=next[i]) if (E[i]!=fa)
    {
        DFS(E[i],x);
        f[x][1]+=f[E[i]][0];
        f[x][0]+=max(f[E[i]][1],f[E[i]][0]);
    }
}
 
LL Work(int x)
{
    FindC=0;
    Find_Circle(x,0);
    cu=0;
    DFS(pu,0);
    cu=1;
    DFS(pu,0);
    return max(f[pu][0],f[pu][1]);
}
 
int main()
{
    read(n);
    Ecnt=1;
    for (int i=1,y;i<=n;i++) 
        read(v[i]),read(y),Add_Edge(i,y);
    for (int i=1;i<=n;i++) if (!vis[i]) ans+=Work(i);
    printf("%lld\n",ans);
    return 0;
}