#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 100005

enum Type{
	OPEN,
	CLOSE,
};

int V,root;
int table[NUM],num_nodes[NUM];
int max_child[NUM],out_num[NUM],parent[NUM];
char buf[NUM];
deque<ll> dp[2][NUM];
vector<int> G[NUM];


void dfs(int node_id,int pre_node){

	parent[node_id] = pre_node;

	for(int i = 0; i < G[node_id].size(); i++){

		if(G[node_id][i] == pre_node)continue;

		dfs(G[node_id][i],node_id);
		out_num[node_id]++;
	}

	int maximum = 0,max_id = -1,child;

	for(int i = 0; i < G[node_id].size(); i++){

		child = G[node_id][i];

		if(child == pre_node)continue;

		num_nodes[node_id] += num_nodes[child];

		if(maximum < num_nodes[child]){

			maximum = num_nodes[child];
			max_id = child;
		}
	}
	max_child[node_id] = max_id;

}

int another(Type type){

	if(type == OPEN){

		return CLOSE;
	}else{

		return OPEN;
	}
}


int main(){

	scanf("%d",&V);

	for(int i = 0; i < V; i++){

		table[i] = 0;
		num_nodes[i] = 1;
		out_num[i] = 0;
	}

	scanf("%s",buf);

	int from,to;

	for(int loop = 0; loop < V-1; loop++){

		scanf("%d %d",&from,&to);
		from--;
		to--;

		G[from].push_back(to);
		G[to].push_back(from);

		table[from]++;
		table[to]++;
	}

	if(V == 1){

		printf("0\n");
		return 0;
	}

	root = 0;

	dfs(root,-1);

	queue<int> Q;

	ll ans = 0;

	for(int i = 0; i < V; i++){

		if(out_num[i] == 0){
			Q.push(i);
		}
	}

	int tmp_node,child;
	Type type;

	while(!Q.empty()){

		tmp_node = Q.front();
		Q.pop();

		if(buf[tmp_node] == '('){

			type = OPEN;
		}else{

			type = CLOSE;
		}

		if(max_child[tmp_node] == -1){

			dp[OPEN][tmp_node].push_back(0);
			dp[CLOSE][tmp_node].push_back(0);

		}else{

			swap(dp[OPEN][tmp_node],dp[OPEN][max_child[tmp_node]]);
			swap(dp[CLOSE][tmp_node],dp[CLOSE][max_child[tmp_node]]);
		}

		if(dp[another(type)][tmp_node].size() >= 2){

			ans += dp[another(type)][tmp_node][1];
			dp[another(type)][tmp_node].pop_front();

		}else{

			dp[another(type)][tmp_node][0] = 0;
		}

		dp[type][tmp_node].push_front(0);
		dp[type][tmp_node][1]++;


		for(int i = 0; i < G[tmp_node].size(); i++){

			child = G[tmp_node][i];
			if(child == parent[tmp_node] || child == max_child[tmp_node])continue;

			for(int k = 0; k < min(dp[OPEN][child].size(),dp[CLOSE][tmp_node].size()); k++){

				ans += dp[OPEN][child][k]*dp[CLOSE][tmp_node][k];
			}

			for(int k = 0; k < min(dp[CLOSE][child].size(),dp[OPEN][tmp_node].size()); k++){

				ans += dp[CLOSE][child][k]*dp[OPEN][tmp_node][k];
			}

			while(dp[type][child].size() >= dp[type][tmp_node].size()){

				dp[type][tmp_node].push_back(0);
			}

			for(int k = 0; k < dp[type][child].size(); k++){

				dp[type][tmp_node][k+1] += dp[type][child][k];
			}

			while(dp[another(type)][child].size() > dp[another(type)][tmp_node].size()+1){

				dp[another(type)][tmp_node].push_back(0);
			}

			for(int k = 0; k < dp[another(type)][child].size()-1; k++){

				dp[another(type)][tmp_node][k] += dp[another(type)][child][k+1];
			}

			dp[OPEN][child].clear();
			dp[CLOSE][child].clear();
		}

		if(parent[tmp_node] == -1)break;

		out_num[parent[tmp_node]]--;
		if(out_num[parent[tmp_node]] == 0){

			Q.push(parent[tmp_node]);
		}
	}

	printf("%lld\n",ans);

	return 0;
}


### Prompt

Please provide a cpp coded solution to the problem described below:

Example

Input

2
()
1 2


Output

1

### Response

```cpp
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 100005

enum Type{
	OPEN,
	CLOSE,
};

int V,root;
int table[NUM],num_nodes[NUM];
int max_child[NUM],out_num[NUM],parent[NUM];
char buf[NUM];
deque<ll> dp[2][NUM];
vector<int> G[NUM];


void dfs(int node_id,int pre_node){

	parent[node_id] = pre_node;

	for(int i = 0; i < G[node_id].size(); i++){

		if(G[node_id][i] == pre_node)continue;

		dfs(G[node_id][i],node_id);
		out_num[node_id]++;
	}

	int maximum = 0,max_id = -1,child;

	for(int i = 0; i < G[node_id].size(); i++){

		child = G[node_id][i];

		if(child == pre_node)continue;

		num_nodes[node_id] += num_nodes[child];

		if(maximum < num_nodes[child]){

			maximum = num_nodes[child];
			max_id = child;
		}
	}
	max_child[node_id] = max_id;

}

int another(Type type){

	if(type == OPEN){

		return CLOSE;
	}else{

		return OPEN;
	}
}


int main(){

	scanf("%d",&V);

	for(int i = 0; i < V; i++){

		table[i] = 0;
		num_nodes[i] = 1;
		out_num[i] = 0;
	}

	scanf("%s",buf);

	int from,to;

	for(int loop = 0; loop < V-1; loop++){

		scanf("%d %d",&from,&to);
		from--;
		to--;

		G[from].push_back(to);
		G[to].push_back(from);

		table[from]++;
		table[to]++;
	}

	if(V == 1){

		printf("0\n");
		return 0;
	}

	root = 0;

	dfs(root,-1);

	queue<int> Q;

	ll ans = 0;

	for(int i = 0; i < V; i++){

		if(out_num[i] == 0){
			Q.push(i);
		}
	}

	int tmp_node,child;
	Type type;

	while(!Q.empty()){

		tmp_node = Q.front();
		Q.pop();

		if(buf[tmp_node] == '('){

			type = OPEN;
		}else{

			type = CLOSE;
		}

		if(max_child[tmp_node] == -1){

			dp[OPEN][tmp_node].push_back(0);
			dp[CLOSE][tmp_node].push_back(0);

		}else{

			swap(dp[OPEN][tmp_node],dp[OPEN][max_child[tmp_node]]);
			swap(dp[CLOSE][tmp_node],dp[CLOSE][max_child[tmp_node]]);
		}

		if(dp[another(type)][tmp_node].size() >= 2){

			ans += dp[another(type)][tmp_node][1];
			dp[another(type)][tmp_node].pop_front();

		}else{

			dp[another(type)][tmp_node][0] = 0;
		}

		dp[type][tmp_node].push_front(0);
		dp[type][tmp_node][1]++;


		for(int i = 0; i < G[tmp_node].size(); i++){

			child = G[tmp_node][i];
			if(child == parent[tmp_node] || child == max_child[tmp_node])continue;

			for(int k = 0; k < min(dp[OPEN][child].size(),dp[CLOSE][tmp_node].size()); k++){

				ans += dp[OPEN][child][k]*dp[CLOSE][tmp_node][k];
			}

			for(int k = 0; k < min(dp[CLOSE][child].size(),dp[OPEN][tmp_node].size()); k++){

				ans += dp[CLOSE][child][k]*dp[OPEN][tmp_node][k];
			}

			while(dp[type][child].size() >= dp[type][tmp_node].size()){

				dp[type][tmp_node].push_back(0);
			}

			for(int k = 0; k < dp[type][child].size(); k++){

				dp[type][tmp_node][k+1] += dp[type][child][k];
			}

			while(dp[another(type)][child].size() > dp[another(type)][tmp_node].size()+1){

				dp[another(type)][tmp_node].push_back(0);
			}

			for(int k = 0; k < dp[another(type)][child].size()-1; k++){

				dp[another(type)][tmp_node][k] += dp[another(type)][child][k+1];
			}

			dp[OPEN][child].clear();
			dp[CLOSE][child].clear();
		}

		if(parent[tmp_node] == -1)break;

		out_num[parent[tmp_node]]--;
		if(out_num[parent[tmp_node]] == 0){

			Q.push(parent[tmp_node]);
		}
	}

	printf("%lld\n",ans);

	return 0;
}


```