[Noip2019]括号树

一.前言

? 回想起去年在考场上的暴力依旧是那么的悲伤……，题目链接。

二.思路

? 首先啊，题目将合法括号串的定义讲的明明白白的了，也就是告诉了我们如何构造合法括号串的方法

• 我们可以在一个合法的括号串外面套一个匹配的括号串
• 我们可以匹配好一个之后和前面紧挨着的合法括号串拼在一起

同时这里声明一下，通过第一种方法构造出来的括号串对于总体来说只算新增了一个，而第二种方法新增的个数取决于前面紧挨着的合法串有多少个。

? 那么开始假设情景，题目已经很明确的告诉了你是在根到当前节点的这一串序列上操作，那么假设我们通过某种方式已经得到了一个串k

? 例如

那么该串各个位上的对于答案分别的贡献为 \(0~0~1~0~1~0\) ,如果记 \(ans[i]\) 表示到第 i 位为止共有多少个合法串的话，那么 ans 数组就应该为 \(0~0~1~1~2~2\)，所以说最终的答案为二。

? 很显然的，ans 数组是为贡献数组的前缀和，而所谓的贡献数组可以换种说法叫做，“以 i 结尾的合法括号串的个数“，那么点缀和也就可以很好地理解了。方便起见我们称贡献数组为 \(f[]\), ans 数组为 \(sum[]\) ,毕竟前缀和。

? 然后用这些数组我们基本上已经可以开始状态转移了。

? 对于一个插入的左括号，很显然，它并不会让答案变多，反而会增加一个寻找匹配的括号。而插入的一个右括号，则是会找到一个左括号去进行匹配并更新答案。很显然的，这个右括号必然会与离它最近的左括号匹配。这里可以反证法

? 若是不与离它最近的左括号 a 进行匹配，反而去跟更远的 b 匹配，那么在 b 和这个右括号之间还有一个孤单的左括号 a 不符合构成合法括号串的定义1.

? 匹配之后当然进行更新答案。这里我们运用到了一个"离它最近的左括号"，可以用数组 \(last[]\) 预处理出来，若是插入一个左括号，直接 last 等于这个左括号就好，如果是一个右括号，则是匹配，更新答案与 \(last[]\),这里放一段核心代码。

		//fa[i]表示父亲，实际上在序列中看等同于上一个括号
		if(a[i]==0){//0是左括号
			last[i]=i;
			f[i]=0LL;
			sum[i]=sum[fa[i]];//直接继承父亲
		}
		else{
			if(last[fa[i]]!=0)f[i]=f[fa[last[fa[i]]]]+1;//注意一定要判断前面的最近左括号有没有
			last[i]=last[fa[last[fa[i]]]];//稍微复杂，可以画图理解
			sum[i]=sum[fa[i]]+f[i];//前缀和奥
		}
		ans^=(i*1LL*sum[i]);

? 那么处理完这些基础问题之后，在这道题中还有一个很关键的点： \(1 ≤ f_u < u1≤f_u<u\) ,那么这个条件有什么作用呢？就是如果我们按照下标以此去计算的话，父亲节点绝对是已经计算过的。这样一遍for就可以啦。

三.CODE

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=5*100001;
int n,a[MAXN],fa[MAXN],last[MAXN];
long long f[MAXN],sum[MAXN],ans;
int main(){
	scanf("%d\n",&n);
	for(int i=1;i<=n;++i)a[i]=getchar()-‘(‘;
	for(int i=2;i<=n;++i)scanf("%d",&fa[i]);
	for(int i=1;i<=n;ans^=(i*1LL*sum[i]),++i)
		if(a[i]==0)last[i]=i,sum[i]=sum[fa[i]];
		else{
			if(last[fa[i]]!=0)f[i]=f[fa[last[fa[i]]]]+1;
			last[i]=last[fa[last[fa[i]]]],sum[i]=sum[fa[i]]+f[i];
		}
	printf("%lld",ans);
	return 0;
}

稍微压了一下行~（其实有更短的 dark 魔法版本……)

[Noip2019]括号树

原文：https://www.cnblogs.com/clockwhite/p/13423301.html