wa #9!!!

记录

玄关玄关玄关玄关玄关玄关玄关玄关

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int h[1145140],e[2145140],ne[2145140],idx;
ll w[1145140],nw[1145140],yw[1145140];
int q[1145140],l=1,r;
int d[1145140],po[1145140];
int st[1145140];
ll op[1145140],cnt[1145140],len;
ll f[1145140][2],ans,dgl=11451400;
ll res;
ll js,hao;
int lp;

inline void add(int a,int b)
{
	idx++;
	ne[idx]=h[a];
	e[idx]=b;
	h[a]=idx;
}

inline void find()
{
	
	for(int i=1;i<=n;i++)
		if(d[i]==1)
		  q[++r]=i;
	  
	while(l<=r)
	{
		//cout<<l<<' ';
		int x=q[l];
		l++;
		d[x]=0;
		st[x]=1;
		//cout<<x<<' ';
		for(int i=h[x];~i;i=ne[i])
		{
			int y=e[i];
			
			if(!st[y])
			{
				//cout<<y<<' ';
				d[y]--;
				if(d[y]==1)
				{
					st[y]=1;
					q[++r]=y;
				}
					
			}
		}
	}
	/*for(int i=0;i<=n-1;i++)
	  cout<<i<<' '<<st[i]<<'\n';*/
	for(int i=1;i<=n;i++)
		if(!st[i])
		{
			op[++len]=i;
			cnt[i]=1;
		}
	
} 

inline void dfs(int x)
{
	st[x]=1;
	int res=0,gen=0;
	for(int i=h[x];~i;i=ne[i])
	{
		int y=e[i];
		if(!st[y]&&!cnt[y])
		{
			dfs(y);
			
			nw[x]+=max(nw[y],yw[y]);
			yw[x]+=nw[y];
			/*res+=nw[y];
			gen+=yw[y];*/
		}
			
	}
	yw[x]+=w[x];
	/*nw[x]=max(res,gen);
	yw[x]=res+w[x];*/
	
}

inline void dfs2(int x)
{
	//cout<<x<<' ';
	po[x]=1;
	st[x]=1;
	int ff=0;
	for(int i=h[x];~i;i=ne[i])
	{
		int y=e[i];
		if(cnt[y]==1&&!st[y])
		{
			ff++;
			dgl=y;
			dfs2(y);
			f[x][1]=max(f[x][1],f[y][0]+yw[x]);
			f[x][0]=max(f[y][0],f[y][1])+nw[x];
			
		}
		
	}
	if(ff==0)
	{
		f[x][1]=yw[x];//yw[x];
		f[x][0]=nw[x];
	}
}

inline void dfs3(int x)
{
	//cout<<x<<' ';
	st[x]=1;
	int ff=0;
	lp++;
	for(int i=h[x];~i;i=ne[i])
	{
		int y=e[i];
		if(lp==1&&y==hao)
		  continue;
		if(cnt[y]==1&&!st[y])
		{
			ff++;
			dfs3(y);
			f[x][1]=max(f[x][1],f[y][0]+yw[x]);
			f[x][0]=max(f[y][0],f[y][1])+nw[x];
			
		}
		
	}
	if(ff==0)
	{
		f[x][1]=yw[x];//yw[x];
		f[x][0]=nw[x];
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0);
	memset(h,-1,sizeof h);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
	  int a,b;	
	  a=i; 
		cin>>w[i];
		cin>>b;
		d[a]++;
		d[b]++;
		
		add(a,b);
		add(b,a);
		
	}
	  
	find();
	
	for(int i=1;i<=len;i++)
	{
		memset(st,0,sizeof st);
		dfs(op[i]);
	}
	
	for(int i=1;i<=len;i++)
	{
		js=0;
		hao=op[i];
		if(!po[hao])
		{
			//cout<<hao<<' ';
			lp=0;
			memset(f,0,sizeof f);
			memset(st,0,sizeof st);
			dfs2(hao);
		  js=max(js,f[hao][0]);
			//cout<<'\n';
			
			memset(f,0,sizeof f);
			memset(st,0,sizeof st);
			dfs3(dgl);
			js=max(js,f[dgl][0]); 
			ans+=js;
		}	
		
		
	}
		
	cout<<ans;
	
	return 0;
}