Example

Input

2
()
1 2


Output

1
#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

int N, subtree[100000], NextPath[100000], idx[100000];
char S[100001];
vector< int > g[100000];
deque< int64 > dp[100000][2];
int64 ret;

void BuildSubTreeSize()
{
  memset(subtree, -1, sizeof(subtree));
  stack< pair< int, int > > s;
  s.emplace(0, -1);
  while(!s.empty()) {
    auto p = s.top();
    s.pop();
    if(~subtree[p.first]) {
      NextPath[p.first] = -1;
      for(auto& to : g[p.first]) {
        if(p.second == to) continue;
        subtree[p.first] += subtree[to];
        if(NextPath[p.first] == -1 || subtree[NextPath[p.first]] < subtree[to]) {
          NextPath[p.first] = to;
        }
      }
    } else {
      s.push(p);
      subtree[p.first] = 1;
      for(auto& to : g[p.first]) {
        if(p.second != to) s.push({to, p.first});
      }
    }
  }
}

void update(int idx)
{
  bool button = S[idx] == '(';
  if(~NextPath[idx]) swap(dp[NextPath[idx]], dp[idx]);
  if(dp[idx][button ^ 1].size() > 1) {
    ret += dp[idx][button ^ 1][1];
    dp[idx][button ^ 1].pop_front();
  } else {
    dp[idx][button ^ 1][0] = 0;
  }
  dp[idx][button].push_front(0);
  ++dp[idx][button][1];
  for(auto& to : g[idx]) {
    if(to == NextPath[idx]) continue;
    auto& dp1 = dp[idx], & dp2 = dp[to];
    for(int j = 0; j < dp2[0].size(); j++) {
      if(j < dp1[1].size()) ret += dp1[1][j] * dp2[0][j];
    }
    for(int j = 0; j < dp2[1].size(); j++) {
      if(j < dp1[0].size()) ret += dp1[0][j] * dp2[1][j];
    }
    for(int j = 0; j < dp2[0].size(); j++) {
      int nextIdx = j + (button ? -1 : 1);
      if(nextIdx < 0) continue;
      while(dp1[0].size() <= nextIdx) dp1[0].push_back(0);
      dp1[0][nextIdx] += dp2[0][j];
    }
    for(int j = 0; j < dp2[1].size(); j++) { // '('
      int nextIdx = j + (button ? 1 : -1);
      if(nextIdx < 0) continue;
      while(dp1[1].size() <= nextIdx) dp1[1].push_back(0);
      dp1[1][nextIdx] += dp2[1][j];
    }
    dp2[0].clear();
    dp2[1].clear();
  }
}

int main()
{
  scanf("%d", &N);
  scanf("%s", S);
  for(int i = 0; i < N - 1; i++) {
    int A, B;
    scanf("%d %d", &A, &B);
    --A, --B;
    g[A].push_back(B);
    g[B].push_back(A);
  }
  for(int i = 0; i < N; i++) {
    dp[i][0].push_back(0);
    dp[i][1].push_back(0);
  }
  BuildSubTreeSize();
  iota(idx, idx + N, 0);
  sort(idx, idx + N, [&](const int& a, const int& b)
  {
    return (subtree[a] < subtree[b]);
  });
  for(int i = 0; i < N; i++) update(idx[i]);
  printf("%lld\n", ret);
}