← 返回题目列表

AtCoder · pakencamp_2023_day1_o

O. 最长的括号子序列

中文机器翻译题面 查看原题

配点 : 600 点

問題文

N 给出了一个有根的顶点树。在顶部 它的编号为 1, 2, \ldots, N ,树的根位于顶部。 1 。 i (1 \le i \le N-1) 第一条边是顶点 A_i 和顶点 表示 B_i 已连接。另外,每个顶点 i 是一个字符 C_i (1 \le i \le N) 已写入。 C_i 为 ( 或 ) 。

下面 有 3 查询类型 您将获得 Q 件,请按顺序处理。 j 第二个查询如下。

  • T_j=1 :顶点 X_j 中写入的字符 更改为 Y_j 对于根为
  • T_j=2 :顶点 S_j 的子树的每个顶点,写入的字符为 输出在 ( 如果 ) , ) 如果 ( 对于根为
  • T_j=3 :顶点 U_j 的顶点 将其更改为 V_j 路径上的顶点(包括两端)写入的字符按顺序排列的字符串的(不一定连续)子字符串中正则括号的最大长度。特别是,空字符串始终是子字符串和常规括号序列,因此始终存在最大值。
什么是(不一定是连续的)子序列? 来自 列 指通过删除 0 或更多元素并在保持其原始顺序的情况下连接剩余元素而创建的序列。 例如 (( 呀 )() 或空字符串 它是 )(() 的子序列, 它不是 (()) 呀 ))) 为 )(() 的子序列。
什么是常规括号序列? 指由 ( 和 ) 组成且满足下列条件之一的字符串。
  • 是一个空字符串
  • 常规括号序列 A 存在, 通过按此顺序连接 (, A, ) 获得
  • 常规括号序列 A, B 存在, 通过按此顺序连接 A, B 获得
例如 (())() 和空字符串是常规括号,但是 ()) 呀 )(( 不是常规括号序列。 当

制約

  • 1 \leq N, Q\leq 2\times 10^5
  • 1 \le A_i < B_i \le N (1 \leq i \leq N-1)
  • C_i=( 或 上面写着字符 C_i=) (1 \leq i \leq N)
  • 1 \leq T_j \leq 3 (1 \leq j \leq Q)
  • T_j=1 时, 1 \le X_j \le N 和 Y_j=( 或 上面写着字符 Y_j=) (1 \leq j \leq Q)
  • T_j=2 时, 1 \le S_j \le N (1 \leq j \leq Q)
  • T_j=3 时, 1 \le U_j, V_j \le N (1 \leq j \leq Q)
  • 所有输入都是整数吗? ( 或 ) 任何一个

入力

输入将以以下格式从标准输入给出。

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
C_1 C_2 \ldots C_N
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

这里,每个查询 \mathrm{query}_i 以下列格式之一给出。 按顺序输出

1 X_i Y_i
2 S_i
3 U_i V_i

出力

T_j=3 查询的答案。


入力例 1

5
1 2
2 3
2 4
4 5
( ( ) ) )
4
3 1 5
3 3 4
2 2
3 5 1

出力例 1

4
2
2

树看起来像这样:

木

每个查询的处理方式如下:

  1. 路径上的顶点是 (1, 2, 4, 5) ,如果连接写在顶点的字符, (()) 。这是一个规则的括号序列,所以长度 4 。
  2. 路径上的顶点是 (3, 2, 4) ,如果连接写在顶点的字符, )() 。该子序列中最长的正则括号序列是 () 所以长度 2 。
  3. 頂点 2 子树的顶点 2, 3, 4, 5 中写入的字符发生变化,顶点 1, 2, 3, 4, 5 中写入的每个字符 (, ), (, (, ( 。
  4. 路径上的顶点是 (5, 4, 2, 1) ,如果连接写在顶点的字符, (()( 。该子序列中最长的正则括号序列是 () 所以长度 2 。

入力例 2

1
(
3
3 1 1
1 1 )
3 1 1

出力例 2

0
0

入力例 3

10
5 6
2 3
2 5
7 8
4 9
2 7
8 10
2 4
1 7
( ) ) ( ) ) ) ) ( (
20
2 2
1 5 )
3 4 9
2 5
3 8 5
3 8 8
2 8
3 9 9
3 7 5
1 1 )
3 4 8
2 9
2 9
2 2
1 5 (
1 6 (
3 2 9
1 2 )
1 5 )
3 4 5

出力例 3

0
0
0
0
0
2
0
2