基环树模板题 90分 WA

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<cstring>
#define ll long long
#define re register int
#define il inline
using namespace std;
il int read()
{
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)&&ch!='-')ch=getchar();
  if(ch=='-')f=-1,ch=getchar();
  while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
  return x*f;
}
il void print(ll x)
{
  if(x<0)putchar('-'),x=-x;
  if(x/10)print(x/10);
  putchar(x%10+'0');
}
il ll max(ll x,ll y){return x>=y?x:y;}
const int N=1e6+5,inf=0x3f3f3f3f;
int n,m,cnt,flag,vis[N],a[N],nxt[N<<1],head[N],tot=1,go[N<<1],st[N],top;
vector<int>r[N];ll f[N][2],g[N][2],ans;
bool b[N];
il void Add(int x,int y)
{
	nxt[++tot]=head[x];
	head[x]=tot;go[tot]=y;
}
il void Tarjan(int x,int p)
{
	if(flag)return;
	st[++top]=x;vis[x]=p;
	for(re i=head[x],y;i,y=go[i];i=nxt[i])
	{
		if(!vis[y])Tarjan(y,p);
		else {
			if(vis[y]!=p)continue;
			flag=1;
			while(st[top]!=y&&st[top]){
				r[p].push_back(st[top]);
				b[st[top]]=1;top--;
			}
			r[p].push_back(y);b[y]=1;
			return;
		}
		if(flag)return;
	}
	if(st[top]==x)top--;
}
il void dfs(int x,int fa)
{
	f[x][1]=a[x];
	for(re i=head[x],y;i,y=go[i];i=nxt[i])
	{
		if(y==fa||b[y])continue;dfs(y,x);
		f[x][1]+=(ll)f[y][0];
		f[x][0]+=(ll)max(f[y][0],f[y][1]);
	}
}
signed main()
{
	n=read();
	for(re i=1,x;i<=n;i++)a[i]=read(),x=read(),Add(x,i);
	for(re i=1;i<=n;i++)
	if(!vis[i]){
		top=flag=0;Tarjan(i,++cnt);
	}
	for(re i=1;i<=cnt;i++)
	{
		if(r[i].size()==0)continue;
		int ans1=0;g[0][0]=g[0][1]=0;
		for(re j=0;j<r[i].size();j++)dfs(r[i][j],0);
		for(re j=1;j<=r[i].size();j++)
		{
			g[j][0]=(ll)max(g[j-1][0],g[j-1][1])+f[r[i][j-1]][0];
			g[j][1]=(ll)max(f[r[i][j-1]][0],f[r[i][j-1]][1])+g[j-1][0];
		}
		ans1=g[r[i].size()][0];
		g[r[i].size()+1][0]=g[r[i].size()+1][1]=0;
		for(re j=r[i].size();j>=1;j--)
		{
			g[j][0]=(ll)max(g[j+1][0],g[j+1][1])+f[r[i][j-1]][0];
			g[j][1]=(ll)max(f[r[i][j-1]][0],f[r[i][j-1]][1])+g[j+1][0];
		}
		ans+=(ll)max(ans1,g[1][0]);
	}
	print(ans);
	return 0;
}

96063967308

96063478172