bzoj1040 [ZJOI2008] 기사 (링 트리 dp)

우선 한 그루의 나무라면 분명히 나무 모양 dp로 해결할 수 있다.하지만 이곳은 나무가 아닐 수도 있고, 고리가 있을 수도 있다.어떡하지?우리가 먼저 이 고리를 찾아낸 다음에 이 변(u, v)을 끊고 각각 u, v를 뿌리로 나무 모양 dp를 한 번 만들면 답은max(dp[u][0], dp[v][0])이다.

#include 
#include 
#include 
#include 
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
#define N 1000010
inline char gc(){
    static char buf[1<<16],*S,*T;
    if(S==T){T=(S=buf)+fread(buf,1,1<<16,stdin);if(T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0,f=1;char ch=gc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc();
    return x*f;
}
int n,a[N],h[N],num=1,u,v;
bool ban[N<<1],vis[N];ll ans=0,dp[N][2];
struct edge{
    int to,next;
}data[N<<1];
inline void add(int x,int y){
    data[++num].to=y;data[num].next=h[x];h[x]=num;
    data[++num].to=x;data[num].next=h[y];h[y]=num;
}
inline void dfs1(int x,int Fa){
    vis[x]=1;
    for(int i=h[x];i;i=data[i].next){
        int y=data[i].to;if(y==Fa) continue;
        if(vis[y]){
            u=x;v=y;ban[i]=ban[i^1]=1;continue;
        }dfs1(y,x);
    }
}
inline void dfs2(int x,int Fa){
    dp[x][0]=0;dp[x][1]=a[x];
    for(int i=h[x];i;i=data[i].next){
        int y=data[i].to;if(y==Fa||ban[i]) continue;
        dfs2(y,x);dp[x][1]+=dp[y][0];dp[x][0]+=max(dp[y][0],dp[y][1]);
    }
}
inline void solve(int rt){
    u=0;v=0;dfs1(rt,0);
    if(!u&&!v){dfs2(rt,0);ans+=max(dp[rt][0],dp[rt][1]);return;}
    dfs2(u,0);ll res=dp[u][0];dfs2(v,0);res=max(res,dp[v][0]);ans+=res;
}
int main(){
//  freopen("a.in","r",stdin);
    n=read();
    for(int i=1;i<=n;++i) a[i]=read(),add(i,read());
    for(int i=1;i<=n;++i) if(!vis[i]) solve(i);
    printf("%lld
",ans);
    return 0;
}