简答题 偏难
#22099

day1-2 括号树

day1-2 括号树


未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;string&gt; using namespace std; int n; string brackets; vector&lt;vector&lt;int&gt;&gt; children; long long ans = 0; void dfs(int u, vector&lt;int&gt;&amp; stack, vector&lt;int&gt;&amp; dp, long long&amp; 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 &gt; 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 &gt;&gt; n;     cin &gt;&gt; brackets;     children.resize(n + 1); // 节点编号从1到n     for (int i = 2; i &lt;= n; ++i) {         int f;         cin &gt;&gt; f;         children[f].push_back(i);     }     vector&lt;int&gt; stack;     vector&lt;int&gt; dp;     long long cnt = 0;     dfs(1, stack, dp, cnt);     cout &lt;&lt; ans &lt;&lt; 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),适用于大规模数据。