洛谷 P5658 [CSP-S 2019] 括号树 题解

题目大意

给定一棵树，每个节点有一个括号。对于每个节点 \(i\)，定义 \(s_i\) 为从根节点到 \(i\) 的路径上所有括号按顺序组成的字符串。求每个 \(s_i\) 中互不相同的合法括号子串的个数 \(k_i\)。
思路

首先，\(k_i\) 可以从父节点递推得到，\(k_i=k_{f_i}+a_i\)。其中 \(a_i\) 为以节点 \(i\) 结尾的合法括号序列数量。因此只要求出每个节点的 \(a\)。
以 ( 为 \(1\) ) 为 \(−1\) 做树上前缀和，设点 \(u\)
的前缀和为 \(sum_u\)。则以 \(u\) 结尾的合法括号子串的开头 \(v\) 需要满足：

• \(sum_{f_v}=sum_u\)。
  
• 对于 \(v\to u\) 这条链上的所有点 \(x\)，有 \(sum_x\ge sum_u\)。
  

在 DFS 过程中开一棵值域线段树维护 \(1\to u\) 这条链上每个 \(sum\) 值对应的最大节点深度。这样就能找到 \(sum_p

感谢分享

热心回复！

用心讨论，共获提升！

新版吗？好像是停更了吧。

分享、互助 让互联网精神温暖你我

很好很强大  我过来先占个楼 待编辑

喜欢鼓捣这些软件，现在用得少，谢谢分享！

很好很强大  我过来先占个楼 待编辑

感谢分享，下载保存了，貌似很强大

不错，里面软件多更新就更好了

过来提前占个楼

懂技术并乐意极积无私分享的人越来越少。珍惜

这个好，看起来很实用