更好的阅读体验

Statement

给定一棵以 $1$ 为根的括号树，每个点恰有一个 ( 或 ) ，定义 $s(i)$ 为将根节点到 $i$ 号点的简单路径按经过顺序排列形成的字符串。

设 $k(i)$ 表示 $s(i)$ 中互不相同的子串是合法括号串的个数。求 $\forall1\leq i\leq n,\sum i\times k(i)$ ，这里的求和表示异或和。

Thoughts & Solution

终于补完模拟赛来继续写题了

题外话：今天模拟赛也有一道括号匹配题，但是是奇妙的贪心，要写两个栈+一个双端队列（

STL永远的神！

显然如果对这棵树进行 DFS ，那么根到 $i$ 的路径上的点可以用栈得到。

那么一遍 DFS 就可以处理出根到 $i$ 的路径上 互不相同的子串是合法括号串 的个数。

设 $endpos[i]$ 为以节点 $i$ 结尾的，根到 $i$ 中互不相同的合法括号子串的个数。类似括号匹配的思路，如果当前为左括号那么直接进栈；如果是右括号且栈不为空，那么栈顶就能和当前点配对，这样就形成了一个新的合法子串 sta.top(),i ，那么当前节点的 $endpos$ 就可以由这一对括号之前的东西推知。

令 $fa[i]$ 表示括号树上点 $i$ 的父亲节点，那么 $endpos[i]=endpos[fa[sta.top()]]+1$ （因为 $endpos[fa[sta.top()]]$ 这些串都能和当前这一对括号接起来，成为一个新的合法子串；或者当前这个单独成串）

最后 $k(i)$ 就是根到 $i$ 的路径上所有的 $endpos$ 之和，这个也可以在 DFS 的时候顺带求出来。

注意递归完之后要记得还原，pop 掉的左括号搞回去，push 的左括号拿出来。

//Author: RingweEH
const int N=5e5+10;
int n,fa[N],endpos[N];
ll f[N];
stack<int> sta;
vector<int> son[N];
char s[N];

void dfs( int u )
{
    bool pu=0; int las=0;
    if ( s[u]=='(' ) sta.push( u ),pu=1;
    else if ( !sta.empty() ) { endpos[u]=endpos[fa[sta.top()]]+1; las=sta.top(); sta.pop(); }
    f[u]=f[fa[u]]+endpos[u];
    for ( int i=0; i<son[u].size(); i++ )
        dfs( son[u][i] );
    if ( pu && sta.top()==u ) sta.pop();
    if ( las ) sta.push( las );
}

int main()
{
    n=read(); scanf( "%s",s+1 );
    for ( int i=2; i<=n; i++ )
        fa[i]=read(),son[fa[i]].push_back(i);

    endpos[1]=0; f[1]=0; dfs( 1 );

    ll ans=0;
    for ( int i=1; i<=n; i++ )
        ans^=(i*f[i]);

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

    return 0;
}