TLE我理解,也不需要通过TLE的点,但是谁能告诉我为啥WA,如何把WA的点AC,最好能有hack(最好短一点),现在是20pts,代码如下:
#include <iostream>
#include <queue>
const int N = 5e5 + 5;
std::string s;
int n,ans = 0,f[N];
struct TreeNode{
char c;
int father,l,r;
TreeNode():father(0),l(0),r(0),c('&'){}
}tree[N];
struct BfsNode{
int x;
std::string ans;
};
bool isValid(std::string s){
int cntL = 0,cntR = 0;
for (char c : s){
if (c == '(') cntL++;
else if (c == ')') cntR++;
if (cntR > cntL) return false;
}
return cntL && cntR && cntL == cntR;
}
std::string S(int i){
std::queue<BfsNode> Q;
Q.push({1,(std::string)"" + tree[1].c});
while (!Q.empty()){
BfsNode Front = Q.front();
Q.pop();
if (tree[Front.x].l != 0) Q.push({tree[Front.x].l,Front.ans + tree[tree[Front.x].l].c});
if (Q.front().x == i) return Q.front().ans;
if (tree[Front.x].r != 0) Q.push({tree[Front.x].r,Front.ans + tree[tree[Front.x].r].c});
if (Q.front().x == i) return Q.front().ans;
}
return "I get NOI Au.";
}
int main(){
std::cin.tie(0)->sync_with_stdio(0);
std::cin >> n >> s;
for (int i = 0;i < s.length();i++) tree[i + 1].c = s[i];
for (int i = 1;i < n;i++){
std::cin >> f[i];
tree[i + 1].father = f[i];
if (tree[f[i]].l == 0) tree[f[i]].l = i + 1;
else tree[f[i]].r = i + 1;
}
for (int i = 1;i <= n;i++){
int cnt = 0;
std::string str = S(i);
for (int j = 0;j < str.length();j++){
std::string sub = "";
for (int k = j;k < str.length();k++){
sub += str[k];
if (isValid(sub)) cnt++;
}
}
ans ^= i * cnt;
}
std::cout << ans << '\n';
return 0;
}