问题 F: 括号树（brackets）（2019 CCF CSP-S2 day1）

问题 F: 括号树（brackets）（2019 CCF CSP-S2 day1）

时间限制: 1 Sec  内存限制: 256 MB
提交: 11  解决: 6
[提交] [状态] [讨论版] [命题人:]

题目描述

输入

 第一行一个整数n，表示树的大小。
第二行一个长为n的由’(’与’)’组成的括号串，第i个括号表示i号结点上的括号。第三行包含n−1个整数，第i（1≤i<n）个整数表示i+1号结点的父亲编号fi+1。

输出

仅一行一个整数表示答案

样例输入 Copy 

5
(()()
1 1 2 2

样例输出 Copy 

6

提示


【样例1解释】
树的形态如下图：
 


将根到1号结点的简单路径上的括号，按经过顺序排列所组成的字符串为(，子串是合法括号串的个数为0。
将根到2号结点的简单路径上的括号，按经过顺序排列所组成的字符串为((，子串是合法括号串的个数为0。
将根到3号结点的简单路径上的括号，按经过顺序排列所组成的字符串为()，子串是合法括号串的个数为1。
将根到4号结点的简单路径上的括号，按经过顺序排列所组成的字符串为(((，子串是合法括号串的个数为0。
将根到5号结点的简单路径上的括号，按经过顺序排列所组成的字符串为(()，子串是合法括号串的个数为1。 
【样例2】
见选手目录下的brackets/brackets2.in 与brackets/brackets2.ans。 
【样例3】
见选手目录下的brackets/brackets3.in 与brackets/brackets3.ans。 
【数据范围】 
测试点编号
n≤
特殊性质
1∼2
8
 
fi =i−1
3∼4
200
5∼7
2000
8∼10
无
11∼14
105
fi =i−1
15∼16
无
17∼20
5×105

 
[提交][状态]