[ZJOI2008]骑士 题解

本题考察基环外向树上的树形dp
首先需要找到环上的任意一条边，然后删去这条边，再对这条边的两个点进行树形dp，最后选择根节点都不选的最大值，就是最后的答案。
根节点都不选的理由是：如果选上根结点，由于环上找出来的这条边切断了，所以在进行树形dp的时候，没有考虑切断的这条边上的另一个点，有可能把那个点选上了，答案会比实际答案大，造成错误。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1000100;
struct node
{
    int v,next;
}e[N<<1];
int head[N];
int val[N];
bool vis[N];
int cnt=0,n;
int pa,pb,pc;
ll ans,f[N][2];
void add(int u,int v)
{
    e[++cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(int u,int pre)
{
    vis[u]=true;
    for(int i=head[u];i;i=e[i].next)
    {
        int to=e[i].v;
        if(!vis[to]) dfs(to,u);
        else if(to!=pre) pa=u,pb=to,pc=(i+1)>>1;
    }
}
void dp(int u,int pre)
{
    f[u][0]=0,f[u][1]=val[u];
    for(int i=head[u];i;i=e[i].next)
    {
        int to=e[i].v;
        if(to!=pre&&((i+1)>>1)!=pc)
        {
            dp(to,u);
            f[u][0]+=max(f[to][1],f[to][0]);
            f[u][1]+=f[to][0];
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int ce,v;
        scanf("%d%d",&ce,&v);
        val[i]=ce;
        add(i,v),add(v,i);
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i]) {
            dfs(i,0);
            dp(pa,0);
            ll va=f[pa][0];
            dp(pb,0);
            ll vb=f[pb][0];
            ans+=max(va,vb);
        }
    }
    printf("%lld\n",ans);
}