自用 放在主页复习
#include<iostream>
#include<unordered_map>
#include<algorithm>
#include<vector>
using namespace std;
const int N=50;
unordered_map<int,int> pos,l,r,judge;//负红,正黑
int pre[N],post[N];
bool st=true,st1=false;
vector<int> vec;
int path[N];
int build(int inl,int inr,int prel,int prer){
int root=pre[prel];
int k=pos[root];
if(inl>k||k>inr){//不是树
st1=false;
return root;
}
if(inl<k)l[root]=build(inl,k-1,prel+1,k-1-inl+prel+1);
if(k<inr)r[root]=build(k+1,inr,k-1-inl+prel+1+1,prer);
return root;
}
void dfs(int u,int deep){//这题数据量比较小,在开一个dfs也能过
if(judge[u]==-1){//如果该节点是红的
if(l.count(u)){
if(judge[l[u]]==-1)st=false;
}
if(r.count(u)){
if(judge[r[u]]==-1)st=false;
}
}
path[deep]=judge[u];
if(!l.count(u)||!r.count(u)){//这里有个坑,注意题目说叶子是空的
int num=0;
for(int i=0;i<=deep;i++)
if(path[i]==1)num++;
vec.push_back(num);
}
if(l.count(u))dfs(l[u],deep+1);
if(r.count(u))dfs(r[u],deep+1);
}
int main(){
int q;
cin>>q;
while(q--){
st=true;
st1=true;
vec.clear();
pos.clear();
l.clear();
r.clear();
int n;
cin>>n;
for(int i=0;i<n;i++){
int x;cin>>x;
if(x<0)x=abs(x),judge[x]=-1;
else judge[x]=1;
pre[i]=x;
post[i]=x;
}
sort(post,post+n);
for(int i=0;i<n;i++)pos[post[i]]=i;
int root=build(0,n-1,0,n-1);
if(!st1){//不是树
puts("No");
continue;
}
if(judge[root]==-1){//根节点是红的
puts("No");
continue;
}
dfs(root,0);
if(!st){//红根的左右孩子不是黑的
puts("No");
continue;
}
int t=vec[0];
bool flag=true;
for(int i=1;i<vec.size();i++){
if(vec[i]!=t)flag=false;
}
if(!flag){//根的左右孩子的黑色节点数量不一致
puts("No");
continue;
}
puts("Yes");
}
}