[洛谷 5658][CSP-S2019]括号树

题目链接

https://www.luogu.org/problem/P5658

题解

因为树上问题和链上问题类似，因此我们先只考虑链上问题。

链上问题最暴力的做法是：对每个终点，两重循环枚举子串，判断子串是否合法，从而把每个终点对应的答案算出来，时间复杂度 \(O(n^3)\)。

注意到如果一个右端点为 \(r\) 的子串合法，那么它会对终点为 \(r,r+1,\ldots,n\) 的答案都会产生贡献，从而我们可以省去枚举终点的过程，只枚举子串。设右端点为 \(i\) 的合法子串个数为 \(f_i\)，则终点 \(i\) 的答案 \(g_i\) 显然为 \(f_i\) 的前缀和，即：

$$g_i=\sum_{j=1}^{i} f_j$$

这样我们就可以将时间复杂度优化到 \(O(n^2)\)。

接下来怎样进一步优化呢？我们考虑合法括号串的递归性质。

如果 A，B 是合法括号串，则 AB 是合法括号串。

如果两个合法括号串相邻，我们可以将其合并为一个更长的合法括号串。当前右括号位置对答案的贡献，则等于之前右括号位置对答案的贡献+1。

判断合法括号串可以用栈来实现。

每个终点的答案仍然是该终点前所有贡献值的前缀和。时间复杂度 \(O(n)\)。

树上做法和链上同理，无非就是多了个回溯的操作。

#include <iostream>
#include <stack>
using namespace std;
struct edge
{
 int v,next;
}e[500005];
long long sum[500005],res[500005];
char s[500005];
int head[500005],fa[500005],cnt;
stack<int> sta;
void addedge(int u,int v)
{
 e[++cnt].v=v;
 e[cnt].next=head[u];
 head[u]=cnt;
}
void dfs(int u)
{
 int p=0;
 if(s[u]==')')
 {
  if(!sta.empty())
  {
   p=sta.top();
   sta.pop();
   res[u]=res[fa[p]]+1;
  }
 }
 else sta.push(u);
 sum[u]=sum[fa[u]]+res[u];
 for(int i=head[u];i;i=e[i].next)
  dfs(e[i].v);
 if(p)sta.push(p);
 else if(!sta.empty())sta.pop();
}
int main()
{
 int n;
 cin>>n;
 cin>>(s+1);
 for(int i=2;i<=n;i++)
 {
  cin>>fa[i];
  addedge(fa[i],i);
 }
 dfs(1);
 long long ans=0;
 for(int i=1;i<=n;i++)
  ans^=(sum[i]*i);
 cout<<ans<<endl;
 return 0;
}