洛谷2607 [ZJOI2008] 骑士

又是一道我看了题解才知道怎么做的题，我还是太弱了。

题意

每个骑士都有一个自己痛恨的骑士（不会恨自己），这俩不能在一起，每个骑士有个能力值，问怎么组合使总的能力值最大。

其中骑士的人数 $N\le 10^{6}$ 。

题解

分（看）析（题）题（解）目可以发现，如果将每个关系之间连一个双向边，每个连通块都有且仅有一个环，所以整个图就是一个基环森林，然后拆一条边分成两棵树各跑一遍树形dp即可。

拆开看以后也就是一棵树，相邻的两个节点不能在一起，就跟没有舞会的上司（雾）一样做就行了：

$$\begin{cases} f[x][1]+=f[y][0] \\ f[x][0]+=max(f[y][1],f[y][0]) \end{cases}$$

不过我最初在标记那条被拆的边的时候没有记录标号，而是记录起点终点，然后卡了很久，在@wzx大佬的提醒下才意识到如果两个互相讨厌那么就会出锅，因为两条重合的边不等于双向边，如果按照起点和终点拆就意味着重合的边中有一条不需要拆的会被拆散，从而gg。

还有要注意开long long，我因为看了题解所以没踩中这个坑。

struct Edge{
    ll next,to;
} edge[2000005];
ll n,m,a,b,c,cnt=1,head[1000005],s[1000005],f[1000005][2],ans,now,edgeid;
bool vis[1000005];

inline void add(ll u,ll v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void find(int x,int fa)
{
    vis[x]=1;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==fa) continue;
        if (vis[y])
        {
            a=x; b=y;
            edgeid=i;
            continue;
        }
        find(y,x);
    }
}

void dfs(int x,int fa)
{
    f[x][1]=s[x];
    f[x][0]=0;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (i==edgeid || (i^1)==edgeid || y==fa) continue;
        dfs(y,x);
        f[x][1]+=f[y][0];
        f[x][0]+=max(f[y][0],f[y][1]);
    }
}

int main()
{
    n=read();
    for (int i=1;i<=n;i++)
    {
        s[i]=read(); m=read();
        add(m,i);
        add(i,m);
    }
    for (int i=1;i<=n;i++)
    {
        if (vis[i]) continue;
        find(i,0);
        dfs(a,0);
        now=f[a][0];
        dfs(b,0);
        ans+=max(now,f[b][0]);
    }
    printf("%lld",ans);
    return 0;
}