注意到有兩個(gè)fii-1,也就是說(shuō)他爹必在它前一個(gè)位置即這棵樹(shù)退化成一條鏈直接暴力枚舉所有情況再寫(xiě)一個(gè)check函數(shù)用來(lái)檢查子串是否合法。順帶提一嘴檢查方法為用一個(gè)棧從頭到腳依次壓入字符當(dāng)出現(xiàn)“”時(shí)彈出棧頂元素看是否匹配。#includebits/stdc.husingnamespacestd;intn,f[500005],ans0;intm;string s;boolcheck(inti,intj){stackcharst;for(intli;lj;l){if(s[l]()st.push(();else{if(st.empty())returnfalse;st.pop();}}returnst.empty();}intmain(){cinn;cins;s s;for(inti1;in;i){cinf[i];//這玩意兒目前還沒(méi)用}for(inti1;in;i){ans0;for(intl1;ln;l){for(intrl;ri;r)if(check(l,r)){ans;}}m^(i*ans);}coutm;return0;}但是這個(gè)方法只能得20分對(duì)我來(lái)說(shuō)足夠了說(shuō)明超時(shí)了我們應(yīng)當(dāng)考慮優(yōu)化算法。因?yàn)闃?shù)已經(jīng)退化成了鏈?zhǔn)浇Y(jié)構(gòu)我們可以想想用dp。咋個(gè)用呢如果當(dāng)前字符是’(直接將序號(hào)入棧如果當(dāng)前字符是 ‘)’1.棧為空說(shuō)明無(wú)法匹配dp[i]02.棧不為空彈出匹配的左括號(hào)位置 pos匹配一對(duì) ()同時(shí) pos 左側(cè)連續(xù)的合法括號(hào)串可以拼接進(jìn)來(lái)。#includebits/stdc.husingnamespacestd;longlongn,f[500005],dp[500005],pos,ans,sum;longlongm;string s;intmain(){cinn;cins;s s;for(longlongi1;in;i){cinf[i];//這玩意兒目前還沒(mé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;}然而還是只有55分?？紤]把第一段和第二段結(jié)合一下滿(mǎn)足鏈?zhǔn)浇Y(jié)構(gòu)時(shí)用dp不滿(mǎn)足時(shí)用個(gè)暴力深搜能多騙一些是一些。#includebits/stdc.husingnamespacestd;intn,m;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()){intpostst.back();st.pop_back();dp[i]dp[post-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(){cinn;cins;for(inti0;in;i){val[i1]s[i];}boolisftrue;vectorintf(n1);for(inti2;in;i){intx;cinx;f[i]x;if(f[i]!i-1)isffalse;G[f[i]].push_back(i);}longlongans;if(isf){ansxdp();}else{ansdfs(1,);}coutans;return0;}這樣就可以再多15分了。但最后還是得寫(xiě)滿(mǎn)分代碼不然寫(xiě)這題解沒(méi)意義?？梢园裠p遷移到樹(shù)上dp[u]dp[f[m]]1。#includebits/stdc.husingnamespacestd;longlongn,sum0,ans0;string s;vectorlonglongG[500005];longlongf[500005];longlongdp[500005];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(){cinn;cins;f[1]0;for(inti2;in;i){cinf[i];G[f[i]].push_back(i);}dfs(1);coutans;return0;}