自动搬运

查看原文

来自洛谷，原作者为

	Inkyo 雪猫猫

搬运于2025-08-24 22:13:03，当前版本为作者最后更新于2019-11-16 20:35:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这里是墨攸，平生没有什么爱好，就喜欢做T2（不好意思这次T2做得我心态炸了）

最完整的题解！不服求超过~~QWQ

2019 - CSP-S DAY-1 T2 括号树

• $\text{Update}$ $19-11-23:$ 修复了一些文本上的小错误。

  话说看的人居然有这么多，真是受宠若惊qwq

---

$ok$和你们聊聊我考场上的心路历程吧：

跟着心路历程走，更容易懂这道题哦！

---

开题。

woc这是什么东西？完全没有思路啊！！！！

想了$10min$，决定先敲个暴力。

1、暴力：10~20pts，复杂度$O(n^4)$，只能解决链

暴力很容易就会了。

因为只解决链，所以不用建树，用一个数组存就可以了。恰好这题很良心，编号为 $i$ 的祖先恰好是 $i-1$，也就是说本身编号就是顺序的（不像毒瘤T3，链的编号还有可能乱序）

先套一重$for$ 枚举 $i$，代表从根节点走到了 $i$ 号节点。由于要计算 $1-i$ 中究竟有多少个子括号序列，所以我们还需要枚举左端点 $l$ 和右端点 $r$，表示枚举到区间为$[l,r]$的子括号序列。然后还要写一个判断括号是否匹配的$check$子函数。子函数的复杂度为$O(r-l)$。

$check$子函数应该都会写吧，开栈来判断即可。具体可以看这题。

$3$重循环套一个$check$，所以复杂度为 $O(n^4)$。实际上是跑不满的，所以有望过 $n=200$ 的数据。

2、55pts，复杂度$O(n)$，只解决链

发现链居然有$55pts$的友好分，果断开链。

观察我们暴力究竟慢在哪里了？无非就是计算 $1-i$ 之中有多少个匹配的括号子序列。

观察数据，发现数据 $5e5$，讲道理 $O(nlogn)$ 跑这样的数据本身就带悬。加上 $\text{CCF}$ 老年机的 $\text{debuff}$ ，还真的没法保证能跑过去。

我深信 $\text{CCF}$ 是不会卡常的 (jiade) ，所以我当时就在想，只能$O(1)$计算每次的贡献值。

怎么 $O(1)$ 计算呢？不知道啊，要不来举几个例子推一推？

注意，以下的例子第一个字符的下标均为$1$

---

例子1：
()()()

我们发现，$i=2$ 的时候，对答案的贡献值为 $1$。而 $i=4$ 的时候，本身 $[3,4]$就有一个满足要求的括号序列，在合并上前面的成为$[1,4]$，同样满足，于是对答案的贡献值就为$2$，再加上前面$[1,2]$本身有的括号序列，总共为 $3$。

$i=6$时同理，总共的贡献值为 $3$，加上前面的有 $3+3=6$ 种。其他位置均没有贡献。

换句话说，$i$为$1-6$时对答案的贡献分别为$0,1,0,2,0,3$，合并后的总答案为$0,1,1,3,3,6$

---

例子2:
())()

继续前面的思想，$i=2$时，对答案贡献$1$。而$i=3$时，由于不满足成匹配的括号序列，所以没有贡献。而$i=5$时，由于$i=3$多了一个后括号，$[1,3]$不匹配，导致$[1,5]$成不了一个匹配的括号序列。故对答案的贡献仍为 $1$

$i$为$1-5$时对答案的贡献分别为$0,1,0,0,1$，合并后的总答案为$0,1,1,1,2$

---

例子3:
()(())

接着刚刚的分析，$i=2$时，贡献为$1$，而$i=5$时，由于$i=3$在中间断开，使$[1,5]$不能匹配，所以贡献仍为$1$。

当$i=6$情况有了变化。我们发现$[1,2]$是匹配的。故$[1,2],[3,6]$能合成一个匹配的序列，故对答案贡献为$2$。

$i$为$1-6$时对答案的贡献分别为$0,1,0,0,1,2$，合并后的总答案为$0,1,1,1,2,4$

---

ok，理论的分析就先告一段落了！有没有发现什么规律？

我们发现，一个后括号如果能匹配一个前括号，假设这个前括号的前$1$位同样有一个已经匹配了的后括号，那么我们势必可以把当前的匹配和之前的匹配序列合并，当前的这个后括号的贡献值，其实就等于前面那个后括号的贡献值$+1$！

这是一个非常重要的结论，可以在递推过程中，直接完成 $O(1)$ 计算贡献值！

你可以用这个结论带入到前面的例子中推一下，马上就明白了（不要嫌麻烦，嫌麻烦就做不了题。考场上就是要多手推）

有了贡献值，当前位置答案总和就很好算了。很明显，第 $i$ 位的总和等于 $i-1$ 位的总和 加上 第 $i$ 位的贡献值。

那怎么判断括号是否匹配呢？ 我们同样可以用这题的思想开栈做。每次压入一个括号然后进行操作即可。

就算后括号匹配了，那我又如何知道前括号的位置呢？ 其实也很简单。我们把压入括号改一改，不压括号，取之而代，压入前括号的位置即可。判断是否匹配只需要看栈里有没有数即可。

我们用 $lst[i]$ 表示第 $i$ 位的贡献，$sum[i]$ 表示第 $i$ 位的答案总合。那么就有：

//s是栈，top是栈顶，手写栈貌似要快很多。

if(c[i] == ')') //是后括号
{
	if(top == 0) continue; //栈为空，则没有匹配
	int t = s[top]; //匹配的前括号的位置 
	lst[i] = lst[t - 1] + 1 //结论计算贡献值
    top --;
}
else if(c[i] == '(') s[++ top] = i; //是前括号，就压入它的位置 
sum[i] = sum[i - 1] +  lst[i]; //计算总和 

很容易发现，这样处理一个位置的总和其实是$O(1)$的

当然整个代码要放进一个循环里。完整代码如下：

for(int i = 1; i <= n; i ++) //好吧只多了个循环....
{
	if(c[i] == ')')
	{
		if(top == 0) continue; //判断栈是否为空 
		int t = s[top]; //匹配的前括号的位置 
		lst[i] = lst[t - 1] + 1 //结论计算贡献值
        top --;
	}
	else if(c[i] == '(') s[++ top] = i; //是前括号，就压入它的位置 
	sum[i] = sum[i - 1] +  lst[i]; //计算总和 
} 

这样，你就有了 55pts 稳稳的分！

2、100pts，复杂度$O(n)$，正解

解决了链，有了稳稳的 55pts。想想好像可以实现化链成树，果断开正解。

很明显，我们解决链的做法在树里有很多行不通的地方。

细细想来，困难主要出现在这$2$个方面。

首先，你没法遍历整颗树的时候编号是连续的。这代表着我们 lst[i] = lst[t - 1] + 1 这样计算是完全行不通了。

其次，遍历一棵树必然会有递归和回溯。而处理链我们不考虑回溯，一直向下找就可以找完了。

但是我们怎么能退缩呢？！大家跟我一起念！（我们遇到什么困难，也不要怕！微笑着面对他....）

咳咳，言归正传，我们来解决这两个问题。

---

先看第一个问题

冷静分析一波，你会发现，虽然编号不连续了，但是你的括号序列一定是从父节点传递下来的！

仔细一想，我们发现，在链的情况里，为什么能用 lst[i] = lst[t - 1] + 1 计算贡献？其实，$t-1$ 就是 $t$ 的父亲节点！无非是 $[t,i]$ 的括号序列继承了 $[1,t-1]$，也就是 $[1,fa[t]]$ 的括号序列！（$fa[i]$ 代表 $i$ 的父亲）

然后我们惊喜的发现，这条定则对于树完全适用。

于是我们就可以修改一波原来的柿子：

lst[i] = lst[t - 1] + 1 $->$ lst[x] = lst[fa[t]] + 1;

$\text{perfect}$！

当然计算总答案也要修改：

sum[i] = sum[i - 1] + lst[i]; $->$ sum[x] = sum[fa[x]] + lst[x];

这样我们就解决了问题$1$

---

接下来考虑解决第二个问题：

在树中遍历有回溯，回溯后栈里的信息可能就无法对应当前的版本...

其实这个问题很容易解决。由于每次回溯只回溯一层，所以我们在回溯的时候，执行我们递归时相反的操作即可！

比如，如果我们扫到右括号，递归时如果栈不为空，照理来说会弹出一个位置信息。

那么我们就可以记录这个信息，回溯的时候再把它压回去，又变成了我们当前的版本。

扫到左括号也一样。我们会压入一个位置信息，那么回溯时，直接弹出这个压入的信息就可以了！

其实这也相当于“复原”操作，让栈里的信息永远留在我们现在的状态！

递归代码就很好写了：

//我使用的链表存图qwq，head,nxt,to都是链表所用（应该都看得懂吧？）

void dfs(int x)
{
	int tmp = 0;
	if(c[x] == ')')
	{
		if(top)
		{
			tmp = s[top];
			lst[x] = lst[fa[tmp]] + 1;
			-- top; 
		}
	}
	else if(c[x] == '(') s[++ top] = x; 
	sum[x] = sum[fa[x]] + lst[x]; //如上所述 
	for(int i = head[x]; i; i = nxt[i])
		dfs(to[i]); //递归 
	//回溯复原操作
	if(tmp != 0) s[++ top] = tmp; //不为 0 代表有信息被弹出 
	else if(top) -- top; 
	//为 0 代表没有弹出，如果栈不为空说明一定压入了一个信息，需要弹出这个信息复原 
}

跑过小数据了，跑过中样例了，跑过大样例了！

恭喜你切了这道题qwq！！

下面就放完整代码吧！

$\text{Code}$

#include<bits/stdc++.h>
#define orz 0
#define inf 0x3f3f3f3f
#define ll long long
#define maxn 500005;

using namespace std;

int n;
char c[maxn];
int head[maxn], nxt[maxn], to[maxn], cnt, fa[maxn];
ll lst[maxn], sum[maxn], ans;
int s[maxn], top;

void add_edge(int u, int v)
{
	nxt[++ cnt] = head[u];
	head[u] = cnt;
	to[cnt] = v;
}

void dfs(int x)
{
	int tmp = 0;
	if(c[x] == ')')
	{
		if(top)
		{
			tmp = s[top];
			lst[x] = lst[fa[tmp]] + 1;
			-- top; 
		}
	}
	else if(c[x] == '(') s[++ top] = x; 
	sum[x] = sum[fa[x]] + lst[x]; //如上所述 
	for(int i = head[x]; i; i = nxt[i])
		dfs(to[i]); //递归 
	//回溯复原操作
	if(tmp != 0) s[++ top] = tmp; //不为 0 代表有信息被弹出 
	else if(top) -- top; 
	//为 0 代表没有弹出，如果栈不为空说明一定压入了一个信息，需要弹出这个信息复原 
}

int main()
{
	scanf("%d", &n);
	scanf("%s", c + 1);
	for(int i = 2; i <= n; i ++)
	{
		int f;
		scanf("%d", &f);
		add_edge(f, i);
		fa[i] = f;
	}
	dfs(1);
	for(int i = 1; i <= n; i ++)
		ans ^= sum[i] * (ll)i;
	printf("%lld", ans);
	return orz;
}

顺带提醒！不仅 $ans$ 要开 $long~long$，$lst$ 和 $sum$ 同样需要！否则你会被构造数据卡得崩溃...

总结

一步一步分析，这道题是不是就没有这么难了？

这也告诉了我们，考场上，一开始绝对不要先想正解，先看一看部分分，对你想正解有帮助哦！

很明显，我们这次解题的步骤就是由 暴力 -> 链 -> 正解的！

---

希望能帮到你们哦！

这篇题解码了287行，写了快1h30min了...可不可以点个大拇指啊QAQ，谢谢各位DALAO啊啊啊啊QAQ