題面
BZOJ
題解
對于每一組厭惡的關系
顯然是連邊操作
如果是一棵樹的話
很顯然的樹型 dp
但是,現在相當于有很多個基環
也就是在一棵樹的基礎上再加了一條邊
這個時候怎麼辦,
暴力拆掉基環(拆掉任意一條邊)
跑兩遍 dp
計算出強制不選兩個點中某一個的最大值
此時就是這個基環的最大值
(不用拆掉所有的邊,因為隻要拆掉一條邊之後可以用樹型 dp 來控制)
可能存在多個聯通塊
是以要算多遍,然後求和
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define MAX 1200000
inline int read()
{
int x=,t=;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-,ch=getchar();
while(ch<='9'&&ch>='0')x=x*+ch-,ch=getchar();
return x*t;
}
struct Line{int v,next;}e[MAX<<];
int h[MAX],cnt=;
int n,a[MAX];
inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}
long long f[MAX][];
int U,V,L;
int fa[MAX],Cri[MAX],tot;
int getf(int x){return x==fa[x]?x:fa[x]=getf(fa[x]);}
void dfs(int u,int ff)
{
f[u][]=a[u];f[u][]=;
for(int i=h[u];i;i=e[i].next)
{
if(i==L||i==(L^))continue;
int v=e[i].v;
if(v==ff)continue;
dfs(v,u);
f[u][]+=max(f[v][],f[v][]);
f[u][]+=f[v][];
}
}
int main()
{
n=read();
for(int i=;i<=n;++i)fa[i]=i;
for(int i=,u;i<=n;++i)
{
a[i]=read(),u=read();Add(u,i),Add(i,u);
if(getf(u)!=getf(i))fa[getf(u)]=getf(i);
else Cri[++tot]=cnt-;
}
long long ans=;
for(int i=;i<=tot;++i)
{
long long ss=;
U=e[Cri[i]].v;V=e[Cri[i]^].v;
L=Cri[i];
dfs(U,);ss=max(ss,f[U][]);
dfs(V,);ss=max(ss,f[V][]);
ans+=ss;
}
printf("%lld\n",ans);
return ;
}