[文章目录]
Description
每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。n<=1000000
第一次知道这个套路，面对只有一个环的树（基环树）的dp，可以断掉环上的一边，分别对两个端点进行树形dp，累计答案。
其实这道题好像是基环森林啊。。。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1001000
typedef long long ll;
int n,head[N],to[N<<1],nxt[N<<1],cnt=1,ed1,ed2,w[N];
ll non[N],sel[N],ans;
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt;
}
void read(int &x)
{
x=0; char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
}
bool vis[N];
void dfs(int x,int pre)
{
vis[x]=1;
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
{
if(vis[to[i]]) {
ed1=i; ed2=i^1;
continue;
}
dfs(to[i],x);
}
}
void solve(int x,int pre)
{
sel[x]=w[x]; non[x]=0;
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre&&i!=ed1&&i!=ed2)
{
solve(to[i],x);
non[x]+=max(sel[to[i]],non[to[i]]);
sel[x]+=non[to[i]];
}
}
int main()
{
scanf("%d",&n); int i,y;
for(i=1;i<=n;++i)
{
read(w[i]); read(y); add(i,y);
}
for(i=1;i<=n;++i)
if(!vis[i])
{
dfs(i,0);
solve(to[ed1],0); ll tmp=non[to[ed1]];
solve(to[ed2],0); ans+=max(tmp,non[to[ed2]]);
}
printf("%lld",ans);
return 0;
}