[CSP-S2019] 括号树

当年我就是死在这个题目上面，错失一等奖
隔着这么久再来做思路还是很清晰的
一个树形动态规划
如果是 ( :dp[u]=dp[fa];
如果是 ）:dp[u]=dp[fa]+x;
其中x是加入）后多出来的字串数，经分析可得x就是连续的括号数
连续的括号可以是（ ）（ （（）） ）【算2个】
我们就要维护一个pre数组
记得要回溯，这里我直接记录栈层就可以避免退栈的过程

#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=5e5+5;
int n;
char c[maxn];
ll dp[maxn],pre[maxn];
int sk[maxn];
vectorQ[maxn];
void calc(int u,int now){
	for(int i=0;i>n;
    for(int i=1;i<=n;i++)cin>>c[i]; 
    for(int i=2,fa;i<=n;i++)cin>>fa,Q[fa].push_back(i);
    if(c[1]=='(')
	    sk[1]=1;
    calc(1,c[1]=='('?1:0);
    ll sum=0;
    for(ll i=2;i<=n;i++){
	sum^=(i*dp[i]);
	//if(i<=20)cout<<"dp[i]="<