Example

Input

2
()
1 2


Output

1
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

const int N=100005;

struct edge{
  int u,v,next;
}G[N<<2];
int head[N],inum;
inline void add(int u,int v,int p){
  G[p].u=u; G[p].v=v; G[p].next=head[u]; head[u]=p;
}
#define V G[p].v
int del[N],size[N];
int sum,minv,rt;
inline void Root(int u,int fa){
  size[u]=1; int maxv=0;
  for (int p=head[u];p;p=G[p].next)
    if (V!=fa && !del[V])
      Root(V,u),size[u]+=size[V],maxv=max(maxv,size[V]);
  maxv=max(maxv,sum-size[u]);
  if (maxv<minv) minv=maxv,rt=u;
}

int val[N];
int cnt1[N],cnt2[N];
ll ans=0;

inline void dfs1(int u,int fa,int d1,int d2,int d3,int d4){
  if (val[u]==-1){
    if (d2) d2--; else d1++;
  }else
    d2++;
  if (val[u]==1){
    if (d3) d3--; else d4++;
  }else
    d3++;
  if (!d2) ans+=cnt1[d1];
  if (!d3) ans+=cnt2[d4];
  for (int p=head[u];p;p=G[p].next)
    if (V!=fa && !del[V])
      dfs1(V,u,d1,d2,d3,d4);
}
inline void dfs2(int u,int fa,int d1,int d2,int d3,int d4){
  size[u]=1;
  if (val[u]==-1){
    if (d2) d2--; else d1++;
  }else
    d2++;
  if (val[u]==1){
    if (d3) d3--; else d4++;
  }else
    d3++;
  if (!d2) cnt2[d1]++;
  if (!d3) cnt1[d4]++;
  for (int p=head[u];p;p=G[p].next)
    if (V!=fa && !del[V])
      dfs2(V,u,d1,d2,d3,d4),size[u]+=size[V];
}

inline void Divide(int u){
  del[u]=1;
  if (val[u]==1) cnt1[1]++;
  if (val[u]==-1) cnt2[1]++;
  for (int p=head[u];p;p=G[p].next)
    if (!del[V]){
      dfs1(V,0,0,0,0,0);
      dfs2(V,0,val[u]==-1,val[u]==1,val[u]==-1,val[u]==1);
    }
  for (int p=head[u];p;p=G[p].next)
    if (!del[V]){
      sum=size[V]; minv=1<<30;
      Root(V,0);
      memset(cnt1,0,sizeof(int)*sum);
      memset(cnt2,0,sizeof(int)*sum);
      Divide(rt);
    }
}

int n;

int main(){
  int iu,iv;
  read(n);
  char c=nc(); for (;!(c=='(' || c==')');c=nc());
  for (int i=1;i<=n;i++) val[i]=c=='('?1:-1,c=nc();
  for (int i=1;i<n;i++)
    read(iu),read(iv),add(iu,iv,++inum),add(iv,iu,++inum);
  sum=n; minv=1<<30; Root(1,0);
  Divide(rt);
  printf("%lld\n",ans);
  return 0;
}