题目分享Y

#include
#include
#include
using namespace std;
#define ll long long
const int maxn=1e6+1;
struct Node
{
int to,next;
}e[maxn<<1],e2[maxn<<1];
int val[maxn];
int head[maxn];
bool vis[maxn];
int head2[maxn];
ll dp[maxn][2];
int sb[2],cnt,cnt2;
void add(int x,int y)
{
e[++cnt].to=y;
e[cnt].next=head[x];
head[x]=cnt;
}
void add2(int x,int y)
{
e2[++cnt2].to=y;
e2[cnt2].next=head2[x];
head2[x]=cnt2;
}
void find_sb(int x,int fa)
{
vis[x]=1;
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
if(v!=fa)
{
if(vis[v])
{
sb[0]=x,sb[1]=v;
continue;
}
add2(v,x);add2(x,v);
find_sb(v,x);
}
}
}
void dfs(int x,int fa)
{
dp[x][1]=(ll)val[x];dp[x][0]=0ll;
for(int i=head2[x];i;i=e2[i].next)
{
int v=e2[i].to;
if(v!=fa)
{
dfs(v,x);
dp[x][0]+=max(dp[v][0],dp[v][1]);
dp[x][1]+=dp[v][0];
}

}
}
int main()
{
int n,x;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&val[i],&x);
add(x,i),add(i,x);
}
ll ans=0;
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
sb[0]=sb[1]=0;find_sb(i,-1);
dfs(sb[0],-1);ll now=dp[sb[0]][0];
dfs(sb[1],-1);ans+=max(now,dp[sb[1]][0]);
}
}
printf("%lld",ans);
return 0;
}