#2 #10TLE,求条
查看原帖
#2 #10TLE,求条
427418
FabricMod楼主2024/10/16 22:20
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
struct node{
	int nxt,to,v;
}a[500100];
char s[500100];//输入的二叉树序列
int h[500100],cnt;//存图
int st[500100],ts;//实现存图所需
int dp[500100][2];//对于以x为根节点的子树,x为绿色或x不为绿色的绿色节点和的最大值
int dpp[500100][2];
int tree[500100][2];
void ae(int x,int y){a[++cnt].nxt=h[x];h[x]=cnt;a[cnt].to=y;}
inline void dfs(int x)
{
	for(int i=h[x];i;i=a[i].nxt)
		dfs(a[i].to);
	dp[x][1]=dp[tree[x][0]][0]+dp[tree[x][1]][0]+1;
	dp[x][0]=max(dp[tree[x][0]][1]+dp[tree[x][1]][0],dp[tree[x][0]][0]+dp[tree[x][1]][1]);
	
	dpp[x][1]=dpp[tree[x][0]][0]+dpp[tree[x][1]][0]+1;
	dpp[x][0]=min(dpp[tree[x][0]][1]+dpp[tree[x][1]][0],dpp[tree[x][0]][0]+dpp[tree[x][1]][1]);
	//对于根不染绿色,不存在两个子树都不染绿色的情况,因为只有三色
}
int main()
{
	scanf("%s",s);
	st[++ts]=1;
	int t=1;
//	for(int i=1;i<=(int)strlen(s);i++)
//		dp[i][1]=1,dpp[i][1]=1;
	for(int i=0,temp=0;i<(int)strlen(s);i++)
	{
		temp=st[ts--];
		if(s[i]=='1')
		{
			ae(temp,++t);
			st[++ts]=t;
			tree[temp][0]=t;
		}
		if(s[i]=='2')
		{
			ae(temp,++t),ae(temp,++t);
			st[++ts]=t,st[++ts]=t-1;
			tree[temp][0]=t-1,tree[temp][1]=t;
		}
	}
	dfs(1);
	cout<<max(dp[1][0],dp[1][1])<<" ";
	cout<<min(dpp[1][0],dpp[1][1]);
}
2024/10/16 22:20
加载中...