bzoj1040(ZJOI2008)骑士——基环树

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1040

基环树的模板。

套路就是把环断开，先把一端作为根节点，强制不选；再把另一端作为根节点，强制不选。

人家的这个判断环的方法真好！还顺便没有连上环的那条边，省下了在函数里判断。

别忘了有多棵基环树！

#include<iostream>

#include<cstdio>

#include<cstring>

#define ll long long

using namespace std;

const int N=1e6+;

int n,m,head[N],xnt,fa[N],rta[N],rtb[N];

ll dp[N][],a[N],ans;

struct Edge{

    int next,to;

    Edge(int n=,int t=):next(n),to(t) {}

}edge[N<<];

int find(int a){return fa[a]==a?a:fa[a]=find(fa[a]);}

void add(int a,int b)

{

    edge[++xnt]=Edge(head[a],b);head[a]=xnt;

    edge[++xnt]=Edge(head[b],a);head[b]=xnt;

    fa[find(a)]=find(b);

}

void sol(int cr,int fa)

{

    dp[cr][]=a[cr];dp[cr][]=;

    for(int i=head[cr],v;i;i=edge[i].next)

    {

        v=edge[i].to;

        if(v==fa)continue;

        sol(v,cr);

        dp[cr][]+=max(dp[v][],dp[v][]);

        dp[cr][]+=dp[v][];

    }

}

int main()

{

    scanf("%d",&n);int tmp;

    for(int i=;i<=n;i++)fa[i]=i;

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

    {

        scanf("%lld%d",&a[i],&tmp);

        if(find(i)!=find(tmp))

            add(i,tmp);

        else rta[++m]=i,rtb[m]=tmp;

    }

    ll c;

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

    {

        sol(rta[i],);c=dp[rta[i]][];

        sol(rtb[i],);c=max(c,dp[rtb[i]][]);

        ans+=c;

    }

    printf("%lld",ans);

    return ;

}