Paranthesis DFS

[Autoratch]

statement

ให้ undi unweighted connected tree แต่ละ node มี '(' หรือ ')' อันใดอันนึงเพียงอันเดียว ขนาด N nodes node: 1 -> N และให้คู่โหนด (U,V)
ถามว่ามีกี่คู่โหนด (x,y) ที่เมื่อสร้างเส้นเชื่อมระหว่าง (x,y) แล้วจะทำให้สามารถ
เดินจาก U ไป V ผ่านเส้นเชื่อม x,y ใหม่ แล้วได้ sequence ที่ valid ; (U->(x-y)->V)
sequence ของ walk คือ sequence วงเลบของแต่ละโหนดที่เดินผ่านมาต่อกัน ต้องเกบทุกอัน ห้ามสลับที่
valid sequence ก็คือ valid paranthesis sequence

concept

ให้ '(' เป็น +1 และ ')' เป็น -1 โดยคานวณ validity จาก sum ของทั้ง seq (ต้องเท่ากับ 0) และ min ของทุก prefix sum (ต้องไม่น้อยกว่า 0)
DFS จาก u ไปทุกโหนด และจาก v ไปทุกโหนด
แต่ละโหนด i เก็บ min ของทุก prefix sum และ sum ของ u->i และ i->v
คู่โหนด (x,y) ที่ใช้ได้ คือคู่ที่ sum(u->x)+sum(y->v) = 0 และ min-prefix-sum(u->x) >= 0 and sum(u->x) >= min-prefix-sum(y->v)
complexity: O(N lg N)

input

บรรทัดแรก มีตัวเลขสามตัว N U V
บรรทัด 2 ถึง N มีตัวเลขสองตัว ui vi แสดงถึงว่า มีเส้นเชื่อมระหว่าง ui vi
บรรทัด N+1 มี string S ยาว N ตัว โดย si (0<=i<N) เป็น '(' หรือ ')' แสดงถึงวงเล็บที่มีในโหนด i+1

output

บรรทัดเดียว มีตัวเลขหนึ่งตัว K แสดงถึงจำนวนคู่โหนด (x,y)

[Autoratch]

subtask

1. N<=200
2. N<=1e3
3. N<=1e5