括号树85分
查看原帖
括号树85分
250699
mot1ve楼主2020/11/4 15:55

为什么pos不能定义在全局变量里?dfs第一行我原来写的是pos=0.但是改成这样才能过

#include<bits/stdc++.h>
#define int long long
using namespace std;
int top,n,idx,ans;
int stack1[1000010],head[1000010],val[1000010],fa[1000010],sum[1000010]; 
char str[1000010];
struct node{
	int nxt,to;
}edge[1000010];
void add(int u,int v)
{
	edge[++idx].nxt=head[u];
	edge[idx].to=v;
	head[u]=idx;
}
void dfs(int x)
{
	int pos=0;//pos=0; 
	if(str[x]=='(')
	stack1[++top]=x;
	else if(str[x]==')')
	{
		if(top!=0)
		{
			pos=stack1[top];
			val[x]=val[fa[pos]]+1;
			top--;
		}
	}
	sum[x]=sum[fa[x]]+val[x];
	for(int i=head[x];i;i=edge[i].nxt)
	{
		int v=edge[i].to;
		dfs(v);
	}
	if(pos!=0)
	{
		stack1[++top]=pos;//多删除的补上
	}
	else if(top)
	{
		top--;//把多加的去掉 
	}
}
signed main()
{
	cin>>n;
	scanf("%s",str+1);
	for(int i=2;i<=n;i++)
	{
		int x;
		scanf("%lld",&x);
		add(x,i);
		fa[i]=x;
	}
	dfs(1);
	for(int i=1;i<=n;i++)
	{
		ans^=1ll*i*sum[i];
	}
	cout<<ans;
	return 0;
}
2020/11/4 15:55
加载中...