【题解】Solution Set - NOIP2024集训Day2 线段树

https://www.becoder.com.cn/contest/5431

「CF1149C」Tree Generator™

结论：

对于括号序列的一个子段，删去所有的匹配括号之后，剩下的不匹配的括号，按顺序构成树上的一条路径。

Why?

从括号序列的构造出发。每次 ( 相当于开始遍历一个点，) 相当于结束遍历一个点。

删掉之后的括号序列，一定是形如 ...)))((((... 的。

相当于是先从一个点开始向上跳，然后一堆匹配的括号，相当于是跳过这整个子树，然后再不断向下跳。

推论：

一棵树的直径即为其括号序列的任意子段的不匹配括号数量的最大值。

Why?

跟上面思路类似，可以证明树上的任意一条路径都可以被括号序列的一段子段表示。

然后，就可以正式开始这道题了。