P2607 [ZJOI2008]骑士

　　这道题我写了一个小时，一直在想有关环的问题……

　　思路应该是有的，就是对于一个环，在一条边上切一刀，分别对应两个新数dp，更新最优解。

　　问题在于怎么切……

　　我一开始解决方案很麻烦，所以这里就放升级后的代码（洛谷第一个题解虽然能A，但有问题）>\<

　　注意几件事情：

1. 当dp到现在的根时，这个到根的点是不能选的。
2. 每一次找到一个新点，都要记录访问过，否则会重复操作：因为已经访问过的点所在的环已经被处理过，整体已经有局部最优解。

　　代码如下;

#include<cstdio>
#include<iostream>
using namespace std;
#define maxn 2000005
#define inf 9999999
int head[maxn],to[maxn],nxt[maxn],w[maxn],fa[maxn];
bool vis[maxn];
int n,cnt,root;
long long ans,f[maxn][2];
void add(int a,int b)
{
    to[++cnt]=b;
    nxt[cnt]=head[a];
    head[a]=cnt;
}
void dp(int x)
{
    f[x][0]=0,f[x][1]=w[x];
    vis[x]=1;
    for(int i=head[x];i;i=nxt[i])
    {
        int u=to[i];
        if(u!=root)
        {
            dp(u);
            f[x][0]+=max(f[u][0],f[u][1]);
            f[x][1]+=f[u][0];
        }
        else
            f[x][1]=-inf;
    }
}
void find_cir(int x)
{
    vis[x]=1;
    root=x;
    while(!vis[fa[root]])
    {
        root=fa[root];
        vis[root]=1;
    }
    dp(root);
    long long now=max(f[root][1],f[root][0]);
    root=fa[root];
    dp(root);
    ans+=max(now,max(f[root][1],f[root][0]));
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&w[i],&fa[i]);
        add(fa[i],i);
    }
    for(int i=1;i<=n;i++)
    {
        if(vis[i]) continue;
        find_cir(i);
    }
    printf("%lld",ans);
    return 0;
}