2017.9.24三色二叉樹思想記録

木形dp入門問題,,,,列挙移行すればよい,
f【i】【0】はこの点が緑色でないことを示す
f【i】【1】この点が緑色であることを示し、
隣接と2人の息子を要求するので、次の点を列挙して状況を移せばいいのです
コード:

#include
#include
using namespace std;
#include
vectorv[100005];
int f[100005][2],g[100005][2],tot,wz=-1;
char str[100005];
void dp(int o)
{
	++wz;
	if(str[wz]=='0')
	{
		f[o][0]=g[o][0]=0;
		f[o][1]=g[o][1]=1;		
	}
	if(str[wz]=='1')
	{
		++tot;
		int lin=tot;
		dp(tot);
		f[o][0]=max(f[lin][0],f[lin][1]);
		g[o][0]=min(g[lin][0],g[lin][1]);
		f[o][1]=f[lin][0]+1;		
		g[o][1]=g[lin][0]+1;
	}
	if(str[wz]=='2')
	{
		++tot;
       int lin1=tot;
		dp(tot);
	    ++tot;
		int lin2=tot;
		dp(tot);
		f[o][0]=max(f[lin1][1]+f[lin2][0],f[lin1][0]+f[lin2][1]);	
		f[o][1]=f[lin1][0]+f[lin2][0]+1;
		g[o][0]=min(g[lin1][1]+g[lin2][0],g[lin1][0]+g[lin2][1]);	
		g[o][1]=g[lin1][0]+g[lin2][0]+1;	
    }   
}
int main()
{
	scanf("%s",str);
	dp(++tot);
	printf("%d %d",max(f[1][1],f[1][0]),min(g[1][1],g[1][0]));
}