💡
原文中文，约1800字，阅读约需5分钟。
📝
内容提要
本文解答了两个问题：树的点亮和合法括号序列。第一个问题使用树的深度和树dp方法，求出所有点被点亮所需的回合数。第二个问题使用卡塔兰数和哈希映射，计算满足给定区间的合法括号序列数量。
🎯
关键要点
-
问题A：给定一棵树，初始根节点点亮，求所有点被点亮所需的回合数。
-
分析问题A时，考虑树的深度和树dp方法，dp[i]存储最少回合数和使用的边编号。
-
问题C：计算长度为n的合法括号序列数量，满足给定区间也是合法的。
-
分析问题C时，首先考虑卡塔兰数，然后分析不同区间的合法性。
-
使用哈希映射和前缀和的xor方法处理不连续的状态，区分嵌套和重叠情况。
-
具体实现中使用map记录区间的随机哈希映射和交集数量，利用前缀和计算结果。
-
代码示例中使用随机数生成和哈希映射来优化计算过程。
➡️
