import scala.collection.mutable

object Main extends App {
  import scala.io.StdIn._

  val n = readLine.trim.toInt
  val node = readLine.trim.toCharArray.zipWithIndex.map{
    case ('(', i) ⇒ new Node(i, Start)
    case (')', i) ⇒ new Node(i, End)
    case _ ⇒ throw new Exception
  }
  for (_ ← 1 until n){
    val Array(a, b) = readLine.trim.split(' ').map(_.toInt - 1)
    node(a).next.add(node(b))
    node(b).next.add(node(a))
  }
  println(
    calPath(node)
  )
  def calPath(nodes: Array[Node]): Long = {
    val tree: Array[Option[CalculatedTree]] = Array.tabulate(nodes.length){ _ ⇒ None: Option[CalculatedTree]}
    val parent: Array[UnionFindTree[Int]] = Array.tabulate(nodes.length){new UnionFindTree(_)}
    val single: mutable.Queue[CalculatedTree] = mutable.Queue[CalculatedTree]()
    for (i ← nodes.indices){
      if (nodes(i).next.size == 1) {
        tree(i) = Some(new CalculatedTree(nodes(i)))
        single.enqueue(tree(i).get)
      }
    }
    while (single.nonEmpty){
      val top = single.dequeue()
      for (next ← top.root.next){
        next.next.remove(top.root)
        val newCl = tree(parent(next.id).value) match {
          case Some(c) ⇒ top.mergedTo(c)
          case None ⇒ top.mergedTo(next)
        }
        parent(next.id).merge(parent(top.root.id))
        tree(parent(next.id).value) = Some(newCl)
        if (newCl.root.next.size == 1) single.enqueue(newCl)
      }
    }
    tree(parent(0).value).get.innerBalancedPath
  }
  class UnionFindTree[V](private val mValue: V) {
    private var mParent: Option[UnionFindTree[V]] = None
    private var mSize: Int = 1
    private def parent: UnionFindTree[V] = {
      mParent.map(_.parent) match{
        case Some(p) ⇒ {
          mParent = Some(p)
          p
        }
        case None ⇒ this
      }
    }
    def value:V = parent.mValue
    def isSameUnion(that: UnionFindTree[V]): Boolean = parent == that.parent
    def merge(that: UnionFindTree[V]): Unit = {
      if (!isSameUnion(that)){
        val thisParent = parent
        val thatParent = that.parent
        if (thisParent.mSize > thatParent.mSize){
          thatParent.mParent = Some(thisParent)
          thisParent.mSize += thatParent.mSize
        }else {
          thisParent.mParent = Some(thatParent)
          thatParent.mSize += thisParent.mSize
        }
      }
    }
  }
  implicit class ScopedFunc[T](val value: T){
    def also(func: T ⇒ Unit): T = {
      func(value)
      value
    }
    def let[A](func: T ⇒ A): A = {
      func(value)
    }
  }
  sealed trait NodeType
  object Start extends NodeType
  object End extends NodeType
  class Node(val id: Int, val nodeType: NodeType) {
    val next: mutable.Set[Node] = mutable.Set()
  }
  class CalculatedTree(val root: Node,
                       val canBeStart: List[Int] = 0::Nil,
                       val canBeEnd: List[Int] = 0::Nil,
                       val innerBalancedPath: Long = 0) {
    def this(r: Node){
      this(r, if (r.nodeType == Start) 0::1::Nil else 0::Nil, if (r.nodeType == End) 0::1::Nil else 0::Nil)
    }
    private def mergeStart(a: List[Int], b: List[Int]): List[Int] = {
      (a, b) match{
        case (ah::at, bh::bt) ⇒ ah + bh :: mergeStart(at, bt)
        case (Nil, _) ⇒ b
        case (_, Nil) ⇒ a
      }
    }
    private def calPattern(a: List[Int], b:List[Int]): Long = {
      (a, b) match{
        case (ah::at, bh::bt) ⇒ ah.toLong * bh + calPattern(at, bt)
        case _ ⇒ 0
      }
    }
    private def calInnerPattern(that: CalculatedTree): Long ={
      calPattern(canBeStart, that.canBeEnd) + calPattern(canBeEnd, that.canBeStart)
    }
    private def addStart: (List[Int], List[Int]) = {
      (0::canBeStart.head::canBeStart.tail, canBeEnd match {
        case _ ::h2::t ⇒ h2::t
        case _::Nil ⇒ 0::Nil
        case Nil ⇒ throw new Exception
      })
    }
    private def addEnd: (List[Int], List[Int]) = {
      (canBeStart match {
        case _::h2::t ⇒ h2::t
        case _::Nil ⇒ 0::Nil
        case Nil ⇒ throw new Exception
      }, 0::canBeEnd.head :: canBeEnd.tail)
    }
    def mergedTo(that: CalculatedTree): CalculatedTree = {
      val (newCanBeStart, newCanBeEnd) = that.root.nodeType match {
        case Start ⇒ addStart
        case End ⇒ addEnd
      }
      new CalculatedTree(that.root, mergeStart(newCanBeStart, that.canBeStart), mergeStart(newCanBeEnd, that.canBeEnd), innerBalancedPath + that.innerBalancedPath + calInnerPattern(that))
    }
    def mergedTo(that: Node): CalculatedTree = {
      mergedTo(new CalculatedTree(that))
    }
  }
}


Measured memory_bytes: 316628