[CSP-S2 2019]括号树 题解

题目地址：洛谷：P5658 括号树 – 洛谷 | 计算机科学教育新生态

题目背景

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

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

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

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

题目描述

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

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

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

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

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

$$(1\times k_1)\ \text{xor}\ (2\times k_2)\ \text{xor}\ (3\times k_3)\ \text{xor}\ \cdots \ \text{xor}\ (n\times k_n)$$

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

题意简述

一棵 $n$ 个节点的树上每个节点有一个左括号或右括号，求出从树根 1 到每个节点的树链对应的括号序列中不同的合法子串个数。

输入输出格式

输入格式：

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

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

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

第三行包含 $n−1$ 个整数，第 $i$（$1 \le i < n$）个整数表示 $i + 1$ 号结点的父亲编号 $f_{i+1}$。

输出格式：

输出到文件 brackets.out 中。

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

输入输出样例

样例 #1

输入样例#1：

5
(()()
1 1 2 2 

输出样例#1：

6

数据范围

题解

首先考虑如何求出一个括号序列中不同的合法子串数目，这是一个比较经典的括号序列类 DP 问题，它的解法是这样的：

由于括号序列具有 $A$ 合法，则 $(A)$ 合法的可扩展性，因此可以使用栈来完成 DP 的转移。定义 DP 状态 $f(i)$ 表示括号序列 $S$ 中，以 $S_i$ 结尾的合法子串个数。如果 $S_i$ 是左括号，则将 $i$ 放入一个栈中；如果 $S_i$ 是右括号，则向前找到最近的未匹配的左括号位置 $j$ ，这样就可以完成一次匹配，即是 (A) 的状况，因此有以下转移

$$ f(i) = f(j-1)+1 $$

其中，多出来的 $1$ 个合法子串即是 (A) 这一个。向上找未匹配的过程可以用栈实现，在刚才左括号插入的栈中找到栈顶即是最近的未匹配左括号，随后由于该括号已匹配，因此将其弹出栈。

当这个问题上了树，仍然可以用类似的方法解决。同样地定义 $f(u)$ 为从 $1$ 到 $u$ 这条树链对应的括号序列中，以 $S_u$ 结尾的合法子串个数。在树链上向上找到最深的未匹配左括号结点即可。在 DFS 遍历树上节点的过程中，维护这个栈的信息即可。这一部分的细节可以参考代码中的注释。

由于状态定义仅为 $u$ 结尾的合法子串个数， $u$ 节点的答案应是从 $1$ 到 $u$ 的树链上所有节点的 DP 值之和，因此还要做一次 DFS 完成求和。

由于答案可能很大，因此在计算 $u \times f(u)$ 时需要转型成 long long 计算。

代码

UPD：更换了 unsigned long long ，可以通过官方数据。

// Code by KSkun, 2019/11
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <vector>
#include <stack>
#include <utility>

typedef unsigned long long LL;
typedef std::pair<int, int> PII;

inline char fgc() {
	static char buf[100000], * p1 = buf, * p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
		? EOF : *p1++;
}

inline LL readint() {
	LL res = 0, neg = 1; char c = fgc();
	for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
	for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
	return res * neg;
}

inline char readsingle() {
	char c;
	while(!isgraph(c = fgc())) {}
	return c;
}

const int MAXN = 500005;

int n, fa[MAXN];
LL f[MAXN];
char str[MAXN];

std::vector<int> gra[MAXN];
std::stack<int> sta;

void dfs1(int u) {
	int t = -1;
	if (str[u] == ')' && !sta.empty()) {
		t = sta.top();
		sta.pop();
		f[u] += f[fa[t]] + 1;
	} else if (str[u] == '(') {
		sta.push(u);
	}
	for (int v : gra[u]) {
		dfs1(v);
	}
	if (str[u] == ')' && t != -1) sta.push(t);
	else if (str[u] == '(') sta.pop();
}

void dfs2(int u) {
	f[u] += f[fa[u]];
	for (int v : gra[u]) {
		dfs2(v);
	}
}

int main() {
	scanf("%d", &n);
	scanf("%s", str + 1);
	for (int i = 2; i <= n; i++) {
		scanf("%d", &fa[i]);
		gra[fa[i]].push_back(i);
	}
	dfs1(1);
	dfs2(1);
	LL ans = 0;
	for (int i = 1; i <= n; i++) {
		ans ^= i * f[i];
	}
	printf("%llu", ans);
	return 0;
}