鏈的部分分

我們?cè)O(shè)f[i]表示以i結(jié)尾的括號(hào)序列有多少個(gè)，那么i的實(shí)際答案就是f的前綴和

顯然，所有左括號(hào)和不能匹配的右括號(hào)的f均為0

對(duì)于每一個(gè)能匹配的右括號(hào)i,我們找到與之匹配的左括號(hào)p，以i結(jié)尾的括號(hào)序列就是以p-1結(jié)尾的括號(hào)序列加上p~i這段序列。所以f[i]=f[p-1]+1。

時(shí)間復(fù)雜度?\(O(n)\)?。

滿分做法

發(fā)現(xiàn)實(shí)際上一棵樹在詢問(wèn) u 節(jié)點(diǎn)時(shí)就是一條從 1 到 u 的鏈。那么我們就在dfs過(guò)程中更新括號(hào)匹配和前綴和就行

別把字符串的變量和棧的變量搞混了。最好的辦法是字符串變量大寫

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