洛谷 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