简答题 偏难
#23308

括号树 【题目背景】 本题中合法括号串的定义如下: 1.0是合法括号串。 2.如果A是合法括号串,则(A)是合法括号串。 3.如果A, B是合法括号串,则AB是…

括号树

【题目背景】

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

1.0是合法括号串。

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

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

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

1.字符串S的子串是S中连续的任意个字符组成的字符串。S的子串可用起始位置l与终止位置r来表示,记为S(l,r)(1≤l≤r≤|S|,|S|表示S的长度)。

2.S的两个子串视作不同当且仅当它们在S中的位置不同,即l不同或r不同。

【题目描述】

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

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

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

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

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

(1 x k1) xor (2 x k2) xor (3 x k3)xor .…xor (n x kn)其中xor是位异或运算。

【输入格式】

从文件brackets.in中读入数据。

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

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

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

【输出格式】

输出到文件brackets.out中。

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

【样例1输入】

5

(()()

1 1 2 2

【样例1输出】

6

【样例1解释】

树的形态如下图:

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

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

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

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

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

【数据范围】

未登录也能判分,登录后才会记录
答案与解析
正确答案:<p style="text-align: left;">#include &lt;iostream&gt;</p><p style="text-align: left;">#include &lt;cstdio&gt;</p><p style="text-align: left;">#include &lt;vector&gt;</p><p style="text-align: left;">#include &lt;stack&gt;</p><p> </p><p style="text-align: left;">typedef long long ll;</p><p style="text-align: left;">const int maxn = 500005;</p><p> </p><p style="text-align: left;">std :: vector &lt;int&gt; G[maxn];</p><p style="text-align: left;">std :: stack &lt;int&gt; bra;</p><p> </p><p style="text-align: left;">char str[maxn];</p><p style="text-align: left;">int fa[maxn];</p><p style="text-align: left;">ll con[maxn], k[maxn];</p><p> </p><p style="text-align: left;">void dfs(int u) {</p><p style="text-align: left;">    int num = 0;</p><p style="text-align: left;">    if (str[u] == '(')</p><p style="text-align: left;">        bra.push(u);</p><p style="text-align: left;">    else if (!bra.empty()){</p><p style="text-align: left;">        num = bra.top();</p><p style="text-align: left;">        bra.pop();</p><p style="text-align: left;">        con[u] = con[fa[num]] + 1;</p><p style="text-align: left;">    }</p><p> </p><p style="text-align: left;">    k[u] = k[fa[u]] + con[u];</p><p style="text-align: left;">    for (int i = 0; i &lt; G[u].size(); ++i)</p><p style="text-align: left;">        dfs(G[u][i]);</p><p>    </p><p style="text-align: left;">    if (num != 0)</p><p style="text-align: left;">        bra.push(num);</p><p style="text-align: left;">    else if (!bra.empty())</p><p style="text-align: left;">        bra.pop();</p><p style="text-align: left;">    return ;</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">int main() {</p><p style="text-align: left;">    int n;</p><p style="text-align: left;">    std :: scanf("%d", &amp;n);</p><p style="text-align: left;">    std :: scanf("%s", str + 1);</p><p style="text-align: left;">    for (int i = 2; i &lt;= n; ++i) {</p><p style="text-align: left;">        std :: scanf("%d", &amp;fa[i]);</p><p style="text-align: left;">        G[fa[i]].push_back(i);</p><p style="text-align: left;">    }</p><p style="text-align: left;">    ll ans = 0;</p><p style="text-align: left;">    dfs(1);</p><p style="text-align: left;">    for (int i = 1; i &lt;= n; ++i)</p><p style="text-align: left;">        ans ^= k[i] * (ll)i;</p><p style="text-align: left;">    std :: printf("%lld\n", ans);</p><p style="text-align: left;">    return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。