EERTREE

Let's say we know the set $$$S$$$ of palindrome in range $$$[l,r]$$$ and we want to extend it to range $$$[l,r']$$$. We will maintain an array $$$rp$$$ where $$$rp_i$$$ is the longest palindrome whose right endpoint is at $$$i$$$. Using binary lifting on back edges we can find the longest palindrome whose right endpoint is at $$$x$$$ and is totally contained inside $$$[l,x]$$$, then we simply add it to the set $$$S$$$.

Using small to large trick, it is easy to solve in $$$O(n \log^2 n)$$$.

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
string s;
string t;

int p[200005];
int idx[200005];
int ans[200005];
vector<int> al[200005];
int in[200005];
int out[200005];

int par(int i){
	if (p[i]==i) return i;
	else return p[i]=par(p[i]);
}

int __TIME=0;

void dfs(int i){
	in[i]=__TIME;
	
	if (i<n) t+=s[i];
	else{
		rep(x,0,2){
			dfs(al[i][x]);
			if (x==0) __TIME++;
		}
	}
	
	out[i]=__TIME;
}

int edges[100005][2];
int backedge[100005][18];
int len[100005];

int l[100005];
int r[100005];

int PREV;
int INDEX=1;

int getl(int L,int R){
	int curr=l[L];
	
	rep(x,18,0) if (backedge[curr][x]!=-1 && len[backedge[curr][x]]>(R-L+1)){
		curr=backedge[curr][x];
	}
	
	if (len[curr]>(R-L+1)) curr=backedge[curr][0];
	return curr;
}

int getr(int L,int R){
	int curr=r[R];
	
	rep(x,18,0) if (backedge[curr][x]!=-1 && len[backedge[curr][x]]>(R-L+1)){
		curr=backedge[curr][x];
	}
	
	if (len[curr]>(R-L+1)) curr=backedge[curr][0];
	return curr;
}

set<int> pos[200005];

void dfs2(int i){
	if (i<n){
		pos[i].insert(getl(in[i],in[i]));
	}
	else{
		rep(x,0,2) dfs2(al[i][x]);
		
		int l1=out[al[i][0]]-in[al[i][0]];
		int l2=out[al[i][1]]-in[al[i][1]];
		
		if (l1>l2){
			swap(pos[i],pos[al[i][0]]);
			rep(x,in[al[i][1]],out[al[i][1]]+1){
				pos[i].insert(getr(in[i],x));
			}
		}
		else{
			swap(pos[i],pos[al[i][1]]);
			rep(x,in[al[i][0]],out[al[i][0]]+1){
				pos[i].insert(getl(x,out[i]));
			}
		}
		
		//cout<<idx[i]<<" "<<sz(pos[i])<<endl;
		ans[idx[i]]=sz(pos[i]);
	}
	
	//cout<<i<<" "<<in[i]<<" "<<out[i]<<endl;
	//for (auto it:pos[i]) cout<<it<<" "; cout<<endl;
	//cout<<endl;
}

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n;
	cin>>s;
	
	memset(idx,-1,sizeof(idx));
	rep(x,0,200005) p[x]=x;
	
	int IDX=n;
	
	int a,b;
	rep(x,1,n){
		cin>>a>>b;
		a--,b--;
		
		int aa=par(a),bb=par(b);
		
		al[IDX]={aa,bb};
		p[aa]=p[bb]=IDX;
		idx[IDX]=x;
		IDX++;
	}
	
	dfs(IDX-1);
	
	//cout<<t<<endl;
	//rep(x,0,IDX) cout<<in[x]<<" "<<out[x]<<endl;
	
	memset(edges,-1,sizeof(edges));
	memset(backedge,-1,sizeof(backedge));
	backedge[0][0]=0,backedge[1][0]=0;
	len[0]=-1,len[1]=0;
	
	PREV=0;
	for (int x=0;x<t.size();x++){
		while (t[x-len[PREV]-1]!=t[x]) 
			PREV=backedge[PREV][0];
		
		if (edges[PREV][t[x]-'0']==-1) 
			edges[PREV][t[x]-'0']=++INDEX;
		int curr=edges[PREV][t[x]-'0'];
		len[curr]=len[PREV]+2;
		
		if (len[curr]==1){
			backedge[curr][0]=1;
		}
		else{
			int b=backedge[PREV][0];
			while (t[x-len[b]-1]!=t[x]) b=backedge[b][0];
			backedge[curr][0]=edges[b][t[x]-'0'];
		}
		
		int temp=backedge[curr][0];
		rep(x,0,17){
			if (temp==-1) break;
			temp=backedge[curr][x+1]=backedge[temp][x];
		}
		
		PREV=r[x]=curr;
	}
	
	PREV=0;
	for (int x=t.size()-1;x>=0;x--){
		while (t[x+len[PREV]+1]!=t[x])
			PREV=backedge[PREV][0];
			
		int curr=edges[PREV][t[x]-'0'];
		
		PREV=l[x]=curr;
	}
	
	//rep(x,0,n) cout<<l[x]<<" "; cout<<endl;
	//rep(x,0,n) cout<<r[x]<<" "; cout<<endl;
	
	dfs2(IDX-1);
	
	rep(x,1,n) cout<<ans[x]<<endl;
}

For pairs of ((, we always take the first. For pairs of )), we always take the second.

Now, we have to handle those of type () or )(. Let's take those with ) for now, then we choose which pairs we will change to (.

Notice no matter whether it is () or )( it does a suffix increase on both $$$[a,\infty)$$$ and $$$[b,\infty)$$$. So we can treat them as the same object, lets just denote them as ranges $$$[a,b]$$$.

Now, let's maintain array $$$p$$$ where $$$p_i$$$ is the "balance" of $$$i$$$-th prefix where we only consider taken brackets ("balance" is count of ( minus )). Obviously we want all "balance" to be non-negative.

Let $$$i$$$ be the first index where $$$p_i<0$$$. If there is $$$[a,b]$$$ such that $$$b<i$$$ then it is optimal to take it. Otherwise, take any range $$$a \leq i$$$ where $$$b$$$ is minimized. If there is no such pair that $$$a \leq i$$$, it is impossible.

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct node{
	int s,e,m;
	int val=0,lazy=0;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void propo(){
		if (lazy){
			val+=lazy;
			
			if (s!=e){
				l->lazy+=lazy;
				r->lazy+=lazy;
			}
			
			lazy=0;
		}
	}
	
	void update(int i,int j,int k){
		if (s==i && e==j) lazy+=k;
		else{
			if (j<=m) l->update(i,j,k);
			else if (m<i) r->update(i,j,k);
			else l->update(i,m,k),r->update(m+1,j,k);
			
			l->propo(),r->propo();
			val=min(l->val,r->val);
		}
	}
	
	int query(int i,int j){
		propo();
		
		if (s==i && e==j) return val;
		else if (j<=m) return l->query(i,j);
		else if (m<i) return r->query(i,j);
		else return min(l->query(i,m),r->query(m+1,j));
	}
	
	int find(){
		propo();
		
		if (s==e) return s;
		
		l->propo(),r->propo();
		if (l->val<0) return l->find();
		else return r->find();
	}
} *root;

struct node2{
	int s,e,m;
	ii val;
	node2 *l,*r;
	
	node2 (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		val=ii(1e9,-1);
		if (s!=e){
			l=new node2(s,m);
			r=new node2(m+1,e);
		}
	}
	
	void update(int i,ii k){
		if (s==e) val=k;
		else{
			if (i<=m) l->update(i,k);
			else r->update(i,k);
			
			val=min(l->val,r->val);
		}
	}
	
	ii query(int i,int j){
		if (s==i && e==j) return val;
		else if (j<=m) return l->query(i,j);
		else if (m<i) return r->query(i,j);
		else return min(l->query(i,m),r->query(m+1,j));
	}
} *root2;

int n;
string s;
ii arr[100005];
int ans[100005];

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	int TC;
	cin>>TC;
	while (TC--){
		cin>>n;
		cin>>s;
		rep(x,0,n){
			cin>>arr[x].fi>>arr[x].se;
			arr[x].fi--,arr[x].se--;
		}
		
		if (n%2==1){
			cout<<"-1"<<endl;
			continue;
		}
		
		root=new node(0,2*n);
		root2=new node2(0,2*n);
		
		int num=0;
		rep(x,0,n){
			if (s[arr[x].fi]==s[arr[x].se]){
				if (s[arr[x].fi]=='('){
					ans[x]=0;
					root->update(arr[x].fi,2*n,1);
				}
				else{
					ans[x]=1;
					root->update(arr[x].se,2*n,-1);
				}
			}
			else{
				if (s[arr[x].fi]==')'){
					ans[x]=0;
					root->update(arr[x].fi,2*n,-1);
				}
				else{
					ans[x]=1;
					root->update(arr[x].se,2*n,-1);
				}
				
				num++;
				root2->update(arr[x].fi,{arr[x].se,x});
			}
		}
		
		int tot=root->query(2*n,2*n);
		
		if (tot>0 || tot<-2*num){
			cout<<"-1"<<endl;
			continue;
		}
		
		bool bad=false;
		while (root->query(2*n,2*n)){
			int pos=root->find();
			ii temp=root2->query(0,2*n);
			
			//cout<<temp.fi<<" "<<temp.se<<endl;
			
			int x;
			if (temp.fi<=pos){
				x=temp.se;
			}
			else{
				temp=root2->query(0,pos);
				if (temp.fi==1e9){
					bad=true;
					break;
				}
				
				x=temp.se;
				
			}
			
			root->update(arr[x].fi,2*n,1);
			root->update(arr[x].se,2*n,1);
			root2->update(arr[x].fi,{1e9,-1});
			ans[x]^=1;
		}
		
		if (bad || root->query(0,2*n)<0){
			cout<<"-1"<<endl;
			continue;
		}
		
		rep(x,0,n) cout<<ans[x]<<" "; cout<<endl;
	}
}