题解 P5658 【括号树】
Inkyo
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$子函数应该都会写吧,开栈来判断即可。具体可以看[这题](https://www.luogu.org/problem/P1739)。
$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$ 位的贡献值。
**那怎么判断括号是否匹配呢?** 我们同样可以用[这题](https://www.luogu.org/problem/P1739)的思想开栈做。每次压入一个括号然后进行操作即可。
**就算后括号匹配了,那我又如何知道前括号的位置呢?** 其实也很简单。我们把压入括号改一改,不压括号,取之而代,压入前括号的位置即可。判断是否匹配只需要看栈里有没有数即可。
我们用 $lst[i]$ 表示第 $i$ 位的贡献,$sum[i]$ 表示第 $i$ 位的答案总合。那么就有:
```cpp
//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)$的
当然整个代码要放进一个循环里。完整代码如下:
```cpp
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$
--------------
**接下来考虑解决第二个问题:**
在树中遍历有回溯,回溯后栈里的信息可能就无法对应当前的版本...
其实这个问题很容易解决。由于每次回溯只回溯一层,所以我们在回溯的时候,执行我们递归时相反的操作即可!
比如,如果我们扫到右括号,递归时如果栈不为空,照理来说会弹出一个位置信息。
**那么我们就可以记录这个信息,回溯的时候再把它压回去,又变成了我们当前的版本。**
扫到左括号也一样。**我们会压入一个位置信息,那么回溯时,直接弹出这个压入的信息就可以了!**
其实这也相当于“复原”操作,让栈里的信息永远留在我们现在的状态!
递归代码就很好写了:
```cpp
//我使用的链表存图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}$
```cpp
#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~~