洛谷P5658 [CSP-S2019] 括号树-EW帮帮网

洛谷P5658 [CSP-S2019] 括号树

洛谷题目传送门

题目背景

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

() 是合法括号串。
如果 A 是合法括号串，则 (A) 是合法括号串。
如果 A，B 是合法括号串，则 AB 是合法括号串。

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

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

题目描述

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

小 Q 是一个充满好奇心的小朋友，有一天他在上学的路上碰见了一个大小为 $n$ 的树，树上结点从 $\sim n$ 编号， $1$ 号结点为树的根。除 $1$ 号结点外，每个结点有一个父亲结点， $u$ （ $\leq u \leq n$ ）号结点的父亲为 $f_u$ （ $1 ≤ 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 所有 $\times k_i$ 的异或和，即：
$\times k_1)\ \text{xor}\ (2 \times k_2)\ \text{xor}\ (3 \times k_3)\ \text{xor}\ \cdots\ \text{xor}\ (n \times k_n)$
其中 $x or$ 是位异或运算。

输入格式

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

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

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

输出格式

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

输入输出样例 #1

输入 #1

5
(()()
1 1 2 2

输出 #1

说明/提示

【样例解释1】

树的形态如下图：

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

将根到 2 号结点的字符串为 ((，子串是合法括号串的个数为 $0$ 。

将根到 3 号结点的字符串为 ()，子串是合法括号串的个数为 $1$ 。

将根到 4 号结点的字符串为 (((，子串是合法括号串的个数为 $0$ 。

将根到 5 号结点的字符串为 (()，子串是合法括号串的个数为 $1$ 。

【数据范围】

思路详解

对于每一个串

首先我们先考虑一下我们已经将一个串扣除来的情况：
我们看这个串： $(() ()) (() ()) ()$
我们先定义 $dp_{u}$ 为字符串 $[1, u]$ 中的满足条件的字串数.

$pre_{u}$ 为 $u$ 前有多少个连续的括号，特别的，对于有形如 $(A) [A$ 为一个合法序列 $]$ 的情况，这算作一个连续括号。例如 $(() ()) (() ()) ()$ 为3个连续的括号。

$prel_{u}$ 为 $u$ 前的第一个左括号。
对于每个字符串 $u$ ，我们先分类讨论。

$u = =^{'} (^{'}$ ：
很显然，这种情况下 $dp_{u}=dp_{u-1}$ 。因为当前进来的是一个 $($ ，其不会与前面的拼成括号，所以不需要管。
看似 $u$ 为左括号，它已经不是一个连续的括号，但如果我们后面来了一个右括号，我们好像要用到 $u$ 左边的连续括号数(往下看你便会知道)，所以我们要给他一次机会。若 $u - 1 = =^{'} (^{'}$ 此时有连续的两个左括号，此时就再也连不上了， $pre_{u}=0$ 。否则 $pre_{u}=pre_{u-1}$ 。
对于当前节点，若前一个左括号为 $l$ ，那么 $prel_{u}=l$ 。
$u = =^{'})^{'}$ ：
如果没有前面的左括号与其匹配，那么 $dp_{u}=dp_{u-1}$ 。
同时它的加入使得左边永远无法与右边连接，及 $pre_{u}=0$ 。
由于 $u$ 为右括号，无需更新 $p re l$
如果有左括号与其匹配，那他一定与离他最近的匹配，思考一下对于 $(A)$ ( $() ()$ ，我们往右边加入一个右括号，他与标亮括号匹配，那他会吞掉中间的一块，同时它可以和前面的组成新字串，及 $dp_{u}=dp_{u-1}+pre_{l}+1$ ，其中 $dp_{u-1}"$ 为前面继承的， $" + 1"$ 是新增的括号， $pre_{l}"$ 为与前面组成的新串。
由于新增了一个大括号，但吞掉了中间，所以 $pre_{u}=pre_{l}+1$ 。
由于用掉了 $l$ ，那么要往后退一个，及 $l=prel_{l}$

转到树上

由于这是一棵树，我们发现改变的并不多，只需要将 $u - 1$ 改为 $fa_{u}$ 即可。

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e6+5;
ll n,ans=0;
ll h[N],to[N],ne[N],tot=0;
void add(ll u,ll v){
	tot++;to[tot]=v;ne[tot]=h[u];h[u]=tot;
}
ll a[N],dp[N],pre[N],prel[N];
void dfs(ll u,ll fa,ll l){//u：当前节点，fa：父节点，l：前一个未匹配的左括号
	for(ll i=h[u];i;i=ne[i]){
		ll v=to[i];
		if(v==fa)continue;//防止走回去
		if(a[v]==0){//为'(',由公式可得
			dp[v]=dp[u];
			if(a[u]==0)pre[v]=0;
			else pre[v]=pre[u];
			prel[v]=l;
			dfs(v,u,v);
		}
		else{//由公式
			if(!l){
				pre[v]=0;
				dp[v]=dp[u];
				dfs(v,u,0);
			}
			else{
				dp[v]=dp[u]+pre[l]+1;
				pre[v]=pre[l]+1;
				dfs(v,u,prel[l]);
			}
		}
	}
}
int main(){
	cin>>n;
	for(ll i=1;i<=n;i++){
		char x;cin>>x;
		a[i]=(x==')');//0为左括号'('，1为')'
	}
	for(ll i=2;i<=n;i++){
		ll x;cin>>x;add(i,x);add(x,i);//建边
	}
	ans=0;
	if(a[1]==0)dfs(1,0,1);//记得分类
	else dfs(1,0,0);
	for(int i=1;i<=n;i++)ans=ans^(i*dp[i]);//记住答案是异或和
	cout<<ans;
	return 0;
}
/*高级样例
14
(()())(()())()
1 2 3 4 5 6 7 8 9 10 11 12 13
*/

洛谷P5658 [CSP-S2019] 括号树