简答题
偏难
#22099
day1-2 括号树
day1-2 括号树



答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
#include <vector>
#include <string>
using namespace std;
int n;
string brackets;
vector<vector<int>> children;
long long ans = 0;
void dfs(int u, vector<int>& stack, vector<int>& dp, long long& cnt) {
char c = brackets[u - 1];
int prev_stack_size = stack.size();
int prev_dp_size = dp.size();
long long prev_cnt = cnt;
int prev_left = -1; // 记录弹出的左括号位置,用于回溯
if (c == '(') {
stack.push_back(u);
dp.push_back(0);
} else {
if (!stack.empty()) {
prev_left = stack.back();
stack.pop_back();
int current_dp = (prev_left > 1 ? dp[prev_left - 2] : 0) + 1;
dp.push_back(current_dp);
cnt += current_dp;
} else {
dp.push_back(0);
}
}
ans ^= (long long)u * cnt;
for (int v : children[u]) {
dfs(v, stack, dp, cnt);
}
// 回溯操作,恢复进入当前节点前的状态
dp.pop_back();
if (c == '(') {
stack.pop_back();
} else {
if (prev_left != -1) {
stack.push_back(prev_left);
}
}
cnt = prev_cnt;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
cin >> brackets;
children.resize(n + 1); // 节点编号从1到n
for (int i = 2; i <= n; ++i) {
int f;
cin >> f;
children[f].push_back(i);
}
vector<int> stack;
vector<int> dp;
long long cnt = 0;
dfs(1, stack, dp, cnt);
cout << ans << endl;
return 0;
}</pre><p><br/></p>
解析
方法思路
1、合法括号子串判断:使用栈来匹配括号,维护一个动态规划数组dp,其中dp[i]表示以第i个字符结尾的合法括号子串数量。
2、树的遍历:通过 DFS 遍历树的每个节点,处理每个节点的括号时,维护栈和dp数组,并在回溯时恢复状态,以避免重复计算。
3、状态回溯:进入子节点前记录当前栈、dp数组和合法子串总数的状态,处理完子节点后恢复这些状态,确保每个节点的处理独立。
代码解释
1、输入处理:读取节点数n、括号字符串和父节点信息,构建子节点列表。
2、DFS 遍历:从根节点(节点 1)开始遍历,处理每个节点的括号:
3、左括号:压入栈,dp数组添加 0(以左括号结尾无合法子串)。
4、右括号:若栈非空,弹出栈顶左括号,计算以当前右括号结尾的合法子串数,更新dp和合法子串总数cnt。
5、状态回溯:处理完子节点后,恢复栈、dp数组和cnt到进入当前节点前的状态,确保后续节点处理正确。
6、异或和计算:每个节点处理时,计算i * k_i并累加到异或和ans中。
这种方法确保了每个节点的处理时间为 O (1)(均摊),整体时间复杂度为 O (n),空间复杂度为 O (n),适用于大规模数据。