acwing的latex比较奇怪，建议去My blog 查看

CSP2019 Day1 题解

等我，等我。

[HTML_REMOVED]

T1 格雷码

前面部分的格雷码数量为$2^{n-1}$,后面也是。递归求解即可。注意使用ull类型。

My code

T2 括号树

考虑继承父亲的答案，当前点相比于父亲多出的合法串都一定以该点的字符为右端点。

记$f(u)$表示$u$处新增的合法括号串数量。维护一个栈存左括号，转移时若$u$处字符为右括号则$f(u)=f(StackTop)+1$,否则$f(u)=0$.

复杂度$\mathcal O(n)$.

My code

T3 树上的数

建议边阅读边画图。

首先字典序满足贪心的性质，那么枚举每个数字，通过删边把他放到编号尽量小的节点上，并满足这样操作后，之后存在至少一种方案删完所有边而不影响已确定的数字（包括现在这个）。

关键就在于如何判断现在的移动是否可能做到，以及之后能否还存在方案（请注意，这是两个条件，后面的操作对这两个条件分别处理）。

考虑通过删掉连续的一条链，将一个数移动到一个点上的影响：

• 对于起点，我们钦定了其起始边（即这个与这个点相邻的最早被删掉的边）。
• 对于终点，我们钦定了其最终边（即这个与这个点相邻的最迟被删掉的边）。
• 对于中间部分的点（记为$u$），我们要求其在这条链上的两条边$a,b$满足$a$删除之后立刻删除$b$（这个“立刻”实际是指与$u$相邻的边中$a$删除之后必须删除$b$,但我们很容易通过给$u\rightarrow v$的边和$v\rightarrow u$的边不同的编号来去掉”与$u$相邻”的限制）.记$a$为$b$的前驱，$b$为$a$的后继（这是个偏序关系）。

先考虑一个$\mathcal O(n^3)$的暴力。枚举现在的数字$i$（假设位于$x$），再枚举终点$y$。如果$x$没有起始边，且$y$没有最终边，且中间的点在链上的两条边$a,b$满足$a$没有后继，$b$没有前驱（且$a$不是$b$的间接后继，这个等价于$a,b$还没有任何偏序关系），那么现在这次移动可以做到（但不保证之后还能存在不影响已确定的数的方案）。

考虑什么移动会导致之后不存在不影响已确定的数的方案：对于一个点$u$，若其邻边已经构成了完整的偏序链（起始边到最终边）但$u$仍然有邻边不在偏序链中（说白了就是，我们已知其起始边，那么一直沿着后继走，最后如果走不到终止边那么没有任何问题，如果走到了终止边，且此时已走过的边数不足$deg(u)$,之后就不存在不影响已确定的数的方案了），因为之后还不在该偏序链中的边也必须被删除，这就会导致最终在$u$点的数出去并进来一个新的数。

枚举链上的所有点，用链表维护是否有前驱/后继（为了标明是否是起始边/最终边，可以把点拆两个，让起始边与$u$连，终止边与$n+u$连），用并查集维护是否已经有偏序关系和查询偏序链的长度。

复杂度$\mathcal O(n^3\alpha(n))$

实际上我们只要从$x$开始DFS整棵树，同时判断哪些点可以作为终点，取一个编号最小的就好了，判断能否作为终点的方法同上。

复杂度$\mathcal O(n^2\alpha(n))$

My code