【ZJOI2004】骑士

十五年前的ZJOI而我现在还是切不掉我是不是可以退役了

题目

Z国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。

第一行包含一个正整数N，描述骑士团的人数。接下来N行，每行两个正整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。N ≤ 1 000 000，每名骑士的战斗力都是不大于 1 000 000的正整数

应包含一行，包含一个整数，表示你所选出的骑士军团的战斗力。

Sample Input

Sample Output

30
题目大意：给出n个骑士的战斗力和讨厌的骑士，组成一组没有骑士讨厌另外一个同时战斗力之和最大的骑士组
第一眼看上去我就想到了以前切过的一道傻逼tree dp入门题https://www.luogu.org/problem/P1352
然而这道题是在基环树上做treedp，不巧的是我当时写的时候没有学习基环树，所以光荣爆零了
顺便说下没有上司的舞会，转移为f[x][0]+=max(f[y][0],f[y][1]) f[x][1]+=f[y][0]，显而易见，暴力枚举父亲是否已经被取到
这道题也是同样的原理，即为在基环树上做一遍没有上司的舞会
首先我们需要寻找到一个环，显而易见必定存在一个环（点数和边数相等，且不存在自环和重边的情况）
然后我们设一个bool表示该点能不能走，暴力枚举环上的点能不能走
然后我们可以断开某个节点使之成为一颗普通的树暴力断开即可
做treedp的时候记得特判是不是当前的结点已经被断开了
但是这是个基环树森林，所以要针对每个点求他的答案最后才能累加起来

#include<bits/stdc++.h>
#define int long long
#define fill(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn=1e5+7;
const int N=1e6+10;
const int E=1e6+10;
struct Edge{int next,to;}e[E*2];
int n,ans,qq,head[N],cnt,val[N],ringPt1,ringPt2,not_pass,x,y,dp[N][2];
bool vis[N];
void add(int u,int v){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}void getDP(int rt,int fa){
    dp[rt][0]=0,dp[rt][1]=val[rt];
    for (int i=head[rt];i!=-1;i=e[i].next){
        if (e[i].to==fa) continue;
        if (i==not_pass||i==(not_pass^1)) continue;//这里因为切边所以边的两头都不能走
        getDP(e[i].to,rt);
        dp[rt][0]+=max(dp[e[i].to][0],dp[e[i].to][1]);
        dp[rt][1]+=dp[e[i].to][0];
    }
}void dfs(int rt,int fa){
    vis[rt]=1;
    for (int i=head[rt];i!=-1;i=e[i].next){
        if(e[i].to==fa) continue;
        if(!vis[e[i].to]) dfs(e[i].to,rt);
        else not_pass=i,ringPt1=e[i].to,ringPt2=rt;
        /*这里循环两遍让环的开始节点和结束都能够枚举到*/
    }
}signed main(){
    scanf("%lld",&n);cnt=1;fill(vis,0);fill(head,-1);
    for (int i=1;i<=n;i++){
        scanf("%lld%lld",&x,&y);
        val[i]=x;add(i,y);add(y,i);
    }for (int i=1;i<=n;i++){
        if (vis[i]==1) continue;
        dfs(i,-1);getDP(ringPt1,-1);qq=dp[ringPt1][0];fill(dp,0);
        getDP(ringPt2,-1);qq=max(qq,dp[ringPt2][0]);ans+=qq;
    }printf("%lld
",ans);
    return 0;
}

其实考场上已经差不多想到treedp加一个断开枚举节点的方法但是没敢敲还有最近有人喷我码风不好是怎么回事（疑惑

【ZJOI2004】骑士

题目描述

输入格式

输出格式

样例