【DP】【树形DP】Splot

题意：

分析：

很有毒的树形DP题

每个串联和并联都可以看作：新加一个点，将串（并）联的两个点作为新点的儿子。

然后，可以记录4种状态进行树形DP

转移分串并联讨论一下就可以了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 1000010
#define INF 0x3FFFFFFF
using namespace std;
char s[MAXN];
int tot;
struct node{
	int typ;
	node *ch[2];
	int dp[5];
	int f1,f2,siz;	
}Pool[MAXN];
node *ncnt=Pool,*rt=Pool;
char* build_tree(node *&x,char *s){
	x=++ncnt;
	if(*s=='P'){
		s++;
		x->typ=1;
		x->f1=('o'!=*s++);
		s++;
		s=build_tree(x->ch[0],s);
		s=build_tree(x->ch[1],s);
		s++;
		x->f2=('o'!=*s++); 
		s++;
		x->siz=x->f1+x->f2;
	}
	else if(*s=='S'){
		s++;
		x->typ=2;
		s=build_tree(x->ch[0],s);
		s=build_tree(x->ch[1],s);
		s++;
	}
	else if(*s=='o'){
		s++;
		x->typ=3;
	}
	else if(*s=='x'){
		s++;
		x->typ=4;
		x->siz=1;
	}
	return s;
}
int gmax(int &x,int y){
	x=max(x,y);
}	
void dfs(node *x){
	x->dp[1]=x->dp[2]=x->dp[3]=x->dp[4]=-INF;
	if(x->typ==4){
		x->dp[1]=x->dp[2]=x->dp[3]=1;
		return ;
	}
	if(x->typ==3){
		x->dp[1]=x->dp[2]=x->dp[3]=1;
		x->dp[4]=0;
		return ;
	}
	dfs(x->ch[0]);
	dfs(x->ch[1]);
	x->siz=x->siz+x->ch[0]->siz+x->ch[1]->siz;
	node *l=x->ch[0];
	node *r=x->ch[1];
	if(x->typ==2){
		if(r->siz==0) gmax(x->dp[1],l->dp[1]);
		if(l->siz==0) gmax(x->dp[2],r->dp[2]);
		gmax(x->dp[1],l->dp[4]+r->dp[1]);
		gmax(x->dp[2],l->dp[2]+r->dp[4]);
		gmax(x->dp[3],l->dp[1]+r->dp[2]);
		gmax(x->dp[3],l->dp[3]+r->dp[4]);
		gmax(x->dp[3],l->dp[4]+r->dp[3]);
		gmax(x->dp[4],l->dp[4]+r->dp[4]);
	}
	else if(x->typ==1){
		for(int mask=0;mask<4;mask++){
			int s=mask&1;
			int t=mask&2;
			if(s==0&&x->f1) continue;
			if(t==0&&x->f2) continue;
			if(s&&t){
				if(l->siz==0&&r->siz==0)
					gmax(x->dp[3],2);
			}
			else if(s){
				if(l->siz==0&&r->siz==0)
					gmax(x->dp[1],1);
				gmax(x->dp[2],l->dp[4]+r->dp[2]+1);
				gmax(x->dp[2],l->dp[2]+r->dp[4]+1);
				gmax(x->dp[3],l->dp[2]+r->dp[2]+1);
			}
			else if(t){
				if(l->siz==0&&r->siz==0)
					gmax(x->dp[2],1);
				gmax(x->dp[1],l->dp[4]+r->dp[1]+1);
				gmax(x->dp[1],l->dp[1]+r->dp[4]+1);
				gmax(x->dp[3],l->dp[1]+r->dp[1]+1);
			}
			else{
				gmax(x->dp[1],l->dp[1]+r->dp[1]);
				gmax(x->dp[1],l->dp[4]+r->dp[3]);
				gmax(x->dp[1],l->dp[3]+r->dp[4]);
				
				gmax(x->dp[2],l->dp[2]+r->dp[2]);
				gmax(x->dp[2],l->dp[3]+r->dp[4]);
				gmax(x->dp[2],l->dp[4]+r->dp[3]);
				
				gmax(x->dp[3],l->dp[3]+r->dp[3]);
				
				gmax(x->dp[4],l->dp[4]+r->dp[3]);
				gmax(x->dp[4],l->dp[3]+r->dp[4]);
			}
		}
	}
}
int main(){
	freopen("splot.in","r",stdin);
	freopen("splot.out","w",stdout);
	SF("%s",s);	
	build_tree(rt,s);
	dfs(rt);
	PF("%d",rt->dp[1]);
}