洛谷 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 感谢分享 热心回复！ 用心讨论，共获提升！ 新版吗？好像是停更了吧。 分享、互助 让互联网精神温暖你我 很好很强大我过来先占个楼 待编辑 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 很好很强大我过来先占个楼 待编辑 感谢分享，下载保存了，貌似很强大 不错，里面软件多更新就更好了 过来提前占个楼 懂技术并乐意极积无私分享的人越来越少。珍惜 这个好，看起来很实用 谢谢分享，试用一下 东西不错很实用谢谢分享 谢谢分享，试用一下 yyds。多谢分享 感谢发布原创作品，程序园因你更精彩 谢谢分享，试用一下
页:
[1]
2