P5658 [CSP-S 2019] 括号树 题解
题目链接
我的博客
警示后人
- 请开
long long。 - 如果你开了
long long，但是大样例还是不对。那么，请检查是否使用%d输出。（绝不是因为笔者这里调了一个小时） - 本地运行大样例请先开栈，否则会一直CE。
如何开栈？请在编译选项中添加-Wl,--stack=99824435。
思路
拿到这道题，读完题后首先看样例解释。发现输入输出都是一棵树的形式，因此我们也采用树上递归来求解。
再来看如何求一个字符串中合法括号串的数量。
很容易想到用栈来存储。遇到左括号就进栈，遇到右括号就弹栈。
看一组样例
()()()//下标从 1 开始
我们发现，当 \(i=2\) 时，栈里面有一个左括号，因此弹栈，同时ans++。当 \(i=4\) 时，发现栈里面也有一个左括号。弹栈，ans++。但是我们发现，\(s_1\) 到 \(s_4\) 也可以配对成一个合法的括号串，因此还需要ans++。如何处理这样的情况呢？
这时候我们记一个 \(lst[i]\) 数组，表示 \(i\) 位置（包含）之前的合法括号串的数量。当一个右括号匹配成功后，我们可以累计匹配成功的左括号前面的合法括号串。即 \(lst_i=lst_{pre-1}+1\)，其中 \(pre\) 为匹配的左括号的位置。
如果是在一棵树上呢？我们发现，\(pre-1\) 恰好就是 \(father_{pre}\)。
最终的 \(s_i\) 即为 \(s_{i-1}+lst_i\)。在树上就是 \(s_{father_i}+lst_i\)。
时间复杂度 \(O(n)\)。
代码
const int N=1e6+10;
int n;
ll s[N];//注意所有都要开long long
ll ans;
char c[N];
struct edge{int nxt,to;
}e[N<<1];
int head[N],num_Edge=0;
void add_Edge(int from,int to){//存图e[++num_Edge].nxt=head[from];e[num_Edge].to=to;head[from]=num_Edge;
}
int st[N],top=0;//栈，记录左括号的位置
ll lst[N],fa[N];//lst同上，fa[i] 代表 i 的父亲
void dfs(int x){int t=0;if(c[x]==')'){//当前是右括号，要找有没有左括号与之匹配if(top){//如果有左括号就匹配，没有就不匹配t=st[top];top--;lst[x]=lst[fa[t]]+1;//同上} }else st[++top]=x;//左括号入栈s[x]=s[fa[x]]+lst[x];//同上，统计答案for(int i=head[x];i;i=e[i].nxt){int v=e[i].to;dfs(v);//递归子节点}//回溯。当前节点已经更新完了，他的兄弟节点不需要当前节点更新if(t) st[++top]=t;//如果取出来一个左括号，再加进去else if(top) top--;//如果是压进去一个左括号，弹出来
}
signed main(){
// freopen("brackets.in","r",stdin);
// freopen("brackets.out","w",stdout);n=Read();scanf("%s",c+1);fa[1]=0;for(int i=2;i<=n;i++){int x=Read();add_Edge(x,i);fa[i]=x;}s[0]=0;dfs(1);ans=0ll;for(int i=2;i<=n;i++){ans=ans^(i*s[i]);} printf("%lld\n",ans);//不要忘了%lld输出long long！return 0;
}