TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P6405
  • 题目
  • P6405[CSP-S 2019 Day1]括号树
    限制 : 时间限制 : 20000 MS   空间限制 : 262144 KB
    评测说明 : 1s,256MB
    问题描述

    题目背景

    本题中合法括号串的定义如下:

    1. ()是合法括号串。
    2. 如果A是合法括号串,则(A)是合法括号串。
    3. 如果A,B是合法括号串,则AB是合法括号串。

    本题中子串不同的子串的定义如下:

    1. 字符串$S$的子串是$S$中连续的任意个字符组成的字符串。$S$的子串可用起始位置$l$与终止位置$r$来表示,记为$S(l,r)$($1\leq l\leq r\leq|S|$,$|S|$表示$S$的长度)。
    2. $S$的两个子串视作不同当且仅当它们在$S$中的位置不同,即$l$不同或$r$不同。

    题目描述

    一个大小为$n$的树包含$n$个结点和$n-1$条边,每条边连接两个结点,且任意两个结点间有且仅有一条简单路径互相可达。

    小Q是一个充满好奇心的小朋友,有一天他在上学的路上碰见了一个大小为$n$的树,树上结点从$1\sim n$编号,$1$号结点为树的根。除$1$号结点外,每个结点有一个父亲结点,$u(2\leq u\leq n)$号结点的父亲为$f_u(1\leq f_u<u)$号结点。

    小Q发现这个树的每个结点上恰有一个括号,可能是’(’或’)’。小Q定义$s_i$为:将根结点到$i$号结点的简单路径上的括号,按结点经过顺序依次排列组成的字符串。

    显然$s_i$是个括号串,但不一定是合法括号串,因此现在小Q想对所有的$i(1\leq i\leq n)$求出,$s_i$中有多少个互不相同的子串合法括号串

    这个问题难倒了小Q,他只好向你求助。设$s_i$共有$k_i$个不同子串是合法括号串,你只需要告诉小Q所有$i\times k_i$的异或和,即:

    \[ (1\times k_1)\texttt{ xor }(2\times k_2)\texttt{ xor }(3\times k_3)\texttt{ xor }\dots\texttt{ xor }(n\times k_n) \]

    其中$\texttt{xor}$是位异或运算。

    输入格式

    第一行一个整数$n$,表示树的大小。

    第二行一个长为$n$的由’(’与’)’组成的括号串,第$i$个括号表示$i$号结点上的括号。

    第三行包含$n-1$个整数,第$i(1\leq i<n)$个整数表示$i+1$号结点的父亲编号$f_i+1$。

    输出格式

    仅一行一个整数表示答案。

    样例输入

    5
    (()()
    1 1 2 2

    样例输出

    6

    提示

    样例1解释

    树的形态如下图:

    将根到$1$号结点的简单路径上的括号,按经过顺序排列所组成的字符串为(,子串是合法括号串的个数为0。

    将根到$2$号结点的简单路径上的括号,按经过顺序排列所组成的字符串为((,子串是合法括号串的个数为0。

    将根到$3$号结点的简单路径上的括号,按经过顺序排列所组成的字符串为(),子串是合法括号串的个数为1。

    将根到$4$号结点的简单路径上的括号,按经过顺序排列所组成的字符串为(((,子串是合法括号串的个数为0。

    将根到$5$号结点的简单路径上的括号,按经过顺序排列所组成的字符串为((),子串是合法括号串的个数为1。

    数据范围

    测试点编号 \(\qquad\) \(n\leq\) \(\qquad\) 特殊性质
    1~2 8 \(f_i=i-1\)
    3~4 200 \(f_i=i-1\)
    5~7 2000 \(f_i=i-1\)
    8~10 2000
    11~14 $10^5$ \(f_i=i-1\)
    15~16 $10^5$
    17~20 $5\times 10^5$