CSP-S 2019 D1T2 括号树

题目链接：[https://www.luogu.com.cn/problem/P5658]

思路：

这道题不难。（为什么我在考场上一点思路也没有？？）

假设我们已经处理到树上的节点u（假设1为根节点），那么可以知道：

\([1,u]的合法括号串数=[1,fa[u]]的合法括号串数+u处新增的合法括号串数\)

对于前者，直接继承即可。

对于后者，我们令f[u]表示u节点新增的合法括号串数，栈s表示还未被匹配的‘(’所处在的节点，那么可以得到：

u的字符为‘(’：\(s[++top]=u，f[u]=0\)
u的字符为‘)’：

---- 1. \(top==0\)（即栈为空）\(f[u]=0\)

---- 2. \(top>0\) （即栈非空）\(f[u]=f[fa[s[top]]]+1,top--\)

(意思是u处新得到的合法括号串数要么由\([1,fa[s[top]]\)（即栈顶父亲）\(]\)的合法括号串数加这对括号得到，要么由\(s[top]\)与\(u\)这对括号本身匹配得到)

具体实现：

用数组模拟栈即可。需要注意的是当搜索完部分子树后，栈s中某些元素可能会被覆盖，在这种情况下就需要回溯时在加回去（具体见代码）

注意事项：

做本题时态拘泥于以前的想法与思路，没有跳出来对本题进行分析。只对当前进行求解，没有对所有已求出来的量进行递推求解。

代码：

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=5e5+5;

int n,tot;

ll ans,f[N];

int fi[N],ne[N],to[N],s[N],fa[N];

char ch[N];

inline int read()

{

	int s=0,w=1; char ch=getchar();

	for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;

	for(;isdigit(ch);ch=getchar())s=(s<<1)+(s<<3)+(ch^48);

	return s*w;

}

inline void add(int x,int y)

{

	ne[++tot]=fi[x],fi[x]=tot,to[tot]=y;

}

void dfs(int u,ll pre,int tp)

{

	int pd=0;//pd即用来处理特殊情况的

	if(ch[u]=='(') s[++tp]=u;

	else

	{

		if(!tp) f[u]=0;

		else

		{

			pd=s[tp];//要出栈了，记下此时的栈顶

			f[u]=f[fa[s[tp]]]+1;

			pre+=f[u];

			tp--;

		}

	}

	ans^=(u*pre);

	for(int i=fi[u],v=to[i];i;v=to[i=ne[i]])

		dfs(v,pre,tp);

	if(pd) s[tp+1]=pd;//回溯时再加回来

}

int main()

{

	n=read();

	scanf("%s",ch+1);

	for(int i=2;i<=n;++i)add(fa[i]=read(),i);

	dfs(1,0,0);

	printf("%lld\n",ans);

	return 0;

}

巴特西

CSP-S 2019 D1T2 括号树

题目链接：[https://www.luogu.com.cn/problem/P5658]

思路：

\([1,u]的合法括号串数=[1,fa[u]]的合法括号串数+u处新增的合法括号串数\)

具体实现：

注意事项：

代码：

最新文章

热门文章