[ZJOI2008]骑士

题目链接：Click here

Solution：

可以看出，本题与没有上司的舞会很像，唯一的区别就是它是基环树森林

考虑对于基环树怎么做没有上司的舞会，事实上，环上的相邻的两个点是不可能一起选的，我们从这点下手

我们找到环上任意相邻的两个点，把这条边断开，这样它就变成了一棵树，那么我们对这棵树dp两遍

第一遍，我们钦定一个点不选，第二遍，我们钦定另一个点不选，取两次dp的较大值即可，时间复杂度为(O(n))

Code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+11;
int n,cnt=1,head[N],a[N],fa[N];
int flag,vis[N],tim,is[N],t;
ll f[N][2];
int tot,rt,key,ring[N][2],cut;
struct Edge{int nxt,to;}edge[N<<1];
void ins(int x,int y){
    edge[++cnt].nxt=head[x];
    edge[cnt].to=y;head[x]=cnt;
}
void findc(int x){
    int now=x;
    while(1){
        if(vis[x]==now) break;
        if(vis[x]) return ;
        vis[x]=now;x=fa[x];
    }++tot;t=0;
    while(!is[x]){
        if(t<=2) ring[tot][t++]=x;
        is[x]=1;x=fa[x];
    }
}
void dfs1(int x,int fa){
    f[x][0]=f[x][1]=0;
    for(int i=head[x];i;i=edge[i].nxt){
        int y=edge[i].to;
        if(y==fa) continue;
        if(i==cut||(i^1)==cut) continue;
        dfs1(y,x);
        f[x][0]+=max(f[y][0],f[y][1]);
        f[x][1]+=f[y][0];
    }f[x][1]+=a[x];
}
void dfs2(int x,int fa){
    f[x][0]=f[x][1]=0;
    for(int i=head[x];i;i=edge[i].nxt){
        int y=edge[i].to;
        if(y==fa) continue;
        if(i==cut||(i^1)==cut) continue;
        dfs2(y,x);
        f[x][0]+=max(f[y][0],f[y][1]);
        f[x][1]+=f[y][0];
    }if(x!=key) f[x][1]+=a[x];
}
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
signed main(){
    n=read();ll ans=0;
    for(int i=1;i<=n;i++){
        a[i]=read();int x=read();
        ins(i,x),ins(x,i);fa[i]=x;
    }
    for(int i=1;i<=n;i++) if(!vis[i]) flag=0,findc(i);
    for(int i=1;i<=tot;i++){
        rt=ring[i][0],key=ring[i][1];
        for(int x=head[rt];x;x=edge[x].nxt)
            if(edge[x].to==key){cut=x;break;}
        dfs1(rt,0);ll v=f[rt][0];dfs2(rt,0);
        v=max(v,f[rt][0]);
        v=max(v,f[rt][1]);ans+=v;
    }printf("%lld
",ans);
    return 0;
}