这道题我准备按照考场上的思路从50分到100分写题解开干50分的特例当我们浏览完数据时我们会发现有一个特殊性质Fii-1。这就意味着这棵树退化为了一条链。这时这道题就变成了一道DP模版题括号匹配。当然还是要加一些处理#includebits/stdc.husingnamespacestd;longlongn,f[500005];longlongdp[500005],pos,ans,sum;longlongm;string s;intmain(){cinn;cins;s s;for(longlongi1;in;i){cinf[i];}stacklonglongst;for(longlongi1;in;i){if(s[i](){st.push(i);}else{if(!st.empty()){posst.top();st.pop();dp[i]dp[pos-1]1;}}}for(longlongi1;in;i){sumdp[i];ans^(sum*i);}coutans;return0;}70分通过观察我们可以发现当数据很小时树状的我们可以暴力做出来而链状的我们可以用线性DP做这样可以拿下70分#includebits/stdc.husingnamespacestd;longlongn,f[500005];longlongdp[500005],pos,ans,sum;longlongm;string s;vectorintG[100005];charval[100005];boolcheck(string t){stackintst;for(intl0;lt.size();l){if(t[l](){st.push(();}else{if(st.empty())returnfalse;st.pop();}}returnst.empty();}longlongxdp(){vectorlonglongdp(n1,0);vectorintst;longlongsum0,ans0;for(inti1;in;i){if(s[i-1](){st.push_back(i);dp[i]0;}else{if(!st.empty()){intposst.back();st.pop_back();dp[i]dp[pos-1]1;}else{dp[i]0;}}sumdp[i];ans^(1ll*i*sum);}returnans;}longlongdfs(intu,string path){path.push_back(val[u]);intLpath.size();intk0;for(intl0;lL;l){for(intrl;rL;r){string subpath.substr(l,r-l1);if(check(sub))k;}}longlongans1ll*u*k;for(inti0;iG[u].size();i){intvG[u][i];ans^dfs(v,path);}returnans;}intmain(){cinns;for(inti0;in;i){val[i1]s[i];}boolisftrue;vectorintf(n1);for(inti2;in;i){cinf[i];if(f[i]!i-1)isffalse;G[f[i]].push_back(i);}longlongans;if(isf){ansxdp();}else{ansdfs(1,);}coutans;return0;}正解其实之前我们已经几乎做完了只用把线性DP与树结合在一起做成一个树上DP就行了#includebits/stdc.husingnamespacestd;intn,m;string s;vectorlonglongG[500005];longlongf[500005];longlongdp[500005];longlongsum0,ans0;vectorlonglongst;voiddfs(longlongu){longlongoldsumsum;longlongm-1;if(s[u-1](){st.push_back(u);dp[u]0;}else{if(!st.empty()){mst.back();st.pop_back();dp[u]dp[f[m]]1;}else{dp[u]0;}}sumdp[u];ans^(1LL*u*sum);for(longlongi0;i(longlong)G[u].size();i){dfs(G[u][i]);}sumoldsum;if(s[u-1](){st.pop_back();}else{if(m!-1){st.push_back(m);}}}intmain(){cinns;f[1]0;for(inti2;in;i){cinf[i];G[f[i]].push_back(i);}dfs(1);coutans;return0;}