CSP-S2019

[CSP-S2019] 括号树

题目背景

本题中合法括号串 的定义如下：

1. 合法括号串包括 ()。
2. 假设 A 为一个有效的表达式，则 (A) 被视为一个有效的表达式。
3. 若 A 和 B 均为有效表达式，则将它们连接形成的组合即为有效的表达式。

本题中子串 与不同的子串 的定义如下：

1. 字符串 S 的子串是其 连续部分 内任意选取的若干字符组成的字符串。这些子串可由起始位置 $l$ 和终止位置 $r$ 表示为 $S(l, r)$（其中 $1 \leq l \leq r \leq |S|$ ，且 $|S|$ 表示字符串 $S$ 的长度）。
2. 在字符串 $S$ 中的两个子串被视为不同的 情况仅限于 它们的起始位置或终止位置存在差异。

题目描述

一个规模为n的树由n个节点以及n-1条边构成。每一条边都连接着两个节点，并且任何两个节点之间仅存在一条单一的简单路径使得它们相互可达。

小 Q 对世界充满了好奇，在上学的路上发现了这样一棵拥有 n 个节点的树。这些节点分别以数字 1 到 n 进行编号，并且 1 号节点作为这棵树的根部存在。除了根节点以外的所有子节点都拥有一个父节点，在这里 u（2 ≤ u ≤ n）表示第 u 号子节点的父