随机数据都能过数据把人卡了是什么概念
查看原帖
随机数据都能过数据把人卡了是什么概念
241036
Afoat楼主2020/11/29 11:26

dfs找环

树上dp再套分类讨论

已经拍了一上午了

直接抑郁

#include <bits/stdc++.h>
using namespace std;
int n;
long long ans;
struct Node
{
	int st;
	bool ons;
	int dfn;
	long long val;
	long long dp[2];
}node[1000011];
struct Edge
{
	int des;
	int next;
}edge[2000011];
int cnt=1;
int tail;
int sta[1000011];
long long gan[1000011][2];
inline void Add_edge(int u,int v)
{
	cnt++;
	edge[cnt].des=v;
	edge[cnt].next=node[u].st;
	node[u].st=cnt;
	return;
}
void calc(int poi,int upon)
{
	node[poi].dfn=1;
	node[poi].dp[0]=0ll;
	node[poi].dp[1]=node[poi].val;
	for(int i=node[poi].st;i!=0;i=edge[i].next)
	{
		int flag=edge[i].des;
		if(flag!=upon&&node[flag].ons==0)
		{
			calc(flag,poi);
			node[poi].dp[0]+=max(node[flag].dp[0],node[flag].dp[1]);
			node[poi].dp[1]+=node[flag].dp[0];
		}
	}
	return;
}
inline void Pre(int le,int ri)
{
	for(int i=le;i<=ri;i++)
	{
		gan[i][1]=node[sta[i]].dp[1];
		gan[i][0]=node[sta[i]].dp[0];
	}
	return;
}
bool suc;
void dfs(int poi,int upon)
{
	node[poi].dfn=1;
	tail++;
	sta[tail]=poi;
	
	for(int i=node[poi].st;i!=0;i=edge[i].next)
	{
		if((i^1)==upon)continue;
		
		int flag=edge[i].des;
		if(node[flag].dfn==0)
		{
			dfs(flag,i);
		}
		else
		{
			suc=1;
			int rnm=tail;
			while(sta[rnm]!=flag)
			{
				node[sta[rnm]].ons=1;
				rnm--;
			}
			node[sta[rnm]].ons=1;
			
			rnm=tail;
			while(sta[rnm]!=flag)
			{
				calc(sta[rnm],0);
				rnm--;
			}
			calc(sta[rnm],0);
			
			int fuck=tail-rnm+1;
			
			if(fuck==2)
			{
				ans+=max(node[sta[rnm]].dp[0]+node[sta[tail]].dp[1],max(node[sta[rnm]].dp[1]+node[sta[tail]].dp[0],node[sta[rnm]].dp[0]+node[sta[tail]].dp[0]));
			}
			else if(fuck==3)
			{
				ans+=max(max(node[sta[tail]].dp[0]+node[sta[rnm]].dp[0]+node[sta[rnm+1]].dp[0],node[sta[tail]].dp[0]+node[sta[rnm]].dp[0]+node[sta[rnm+1]].dp[1]),max(node[sta[tail]].dp[0]+node[sta[rnm]].dp[1]+node[sta[rnm+1]].dp[0],node[sta[tail]].dp[1]+node[sta[rnm]].dp[0]+node[sta[rnm+1]].dp[0]));
			}
			else
			{
				int le=rnm+2,ri=tail-1;
				Pre(rnm,tail);
				for(int j=le+1;j<=ri;j++)
				{
					gan[j][1]=gan[j][1]+gan[j-1][0];
					gan[j][0]=gan[j][0]+max(gan[j-1][1],gan[j-1][0]);
				}
				long long flag1=max(gan[ri][0],gan[ri][1])+gan[rnm][1];
				le=rnm+1;
				ri=tail;
				Pre(rnm,tail);
				for(int j=le+1;j<=ri;j++)
				{
					gan[j][1]=gan[j][1]+gan[j-1][0];
					gan[j][0]=gan[j][0]+max(gan[j-1][1],gan[j-1][0]);
				}
				long long flag2=max(gan[ri][0],gan[ri][1])+gan[rnm][0];
				ans+=max(flag1,flag2);
			}
			return;
		}
		
		if(suc==1)
		{
			return;
		}
	}
	tail--;
	return;
}
int main()
{
//	freopen("data.in","r",stdin);
//  freopen("mine.out","w",stdout);
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int to;
		scanf("%lld%d",&node[i].val,&to);
		Add_edge(i,to);
		Add_edge(to,i);
	}
	
	for(int i=1;i<=n;i++)
	{
		if(node[i].dfn==0)
		{
			tail=0;
			suc=0;
			dfs(i,0);
		}
	}
	
	printf("%lld\n",ans);
	
	return 0;
}
/*
3
10 2
20 3
30 1
*/
/*
13
20 3
15 3
36 4
23 5
17 6
32 7
19 8
21 4
30 6
11 7
10 12
20 13
30 11
*/

2020/11/29 11:26
加载中...