链的部分分

我们设f[i]表示以i结尾的括号序列有多少个，那么i的实际答案就是f的前缀和

显然，所有左括号和不能匹配的右括号的f均为0

对于每一个能匹配的右括号i,我们找到与之匹配的左括号p，以i结尾的括号序列就是以p-1结尾的括号序列加上p~i这段序列。所以f[i]=f[p-1]+1。

时间复杂度 \(O(n)\) 。

满分做法

发现实际上一棵树在询问 u 节点时就是一条从 1 到 u 的链。那么我们就在dfs过程中更新括号匹配和前缀和就行

别把字符串的变量和栈的变量搞混了。最好的办法是字符串变量大写

void dfs(ll u) {    if(a[u] == 0) sta[++ top] = u;    else    {        if(top)        {            pei[u] = sta[top];            top --;            f[u] = f[fa[pei[u]]] + 1;            he += f[u];        }    }    ans ^= (he * u);    for(auto v : e[u])    {        if(v == fa[u]) continue;        dfs(v);    }    if(a[u] == 0) top --;    else if(pei[u]) sta[++ top] = pei[u], he -= f[u];      return ; }

链接：https://www.dianjilingqu.com/585603.html