题解

思路

先看长度为 $2$ 的区间 $[i,i+1]$：要让删去某个下标对应的边后两点连通，必须有 $B_i=i+1$ 或 $B_{i+1}=i$。

做法

把 $B_i=i+1$ 记为 R，把 $B_i=i-1$ 记为 L，其余值记为 X。若某处是 R，结合它左侧的二元区间可知左侧也必须一直是 R；L 同理必须一直延伸到右端。由二元区间条件可得，一个好序列的类型串恰好是 R…RXL…L（X 恰有一个）或 R…RL…L（没有 X）。反过来，这两种结构对任意区间都能选取其 R/L 分界处或区间内的 X 作为删边位置，留下的边把连续顶点依次连成树，所以该刻画也是充分的。

预处理 prefix[i] 表示前 $i$ 项都能取为 R，suffix[i] 表示从第 $i$ 项起都能取为 L。枚举没有 X 时的 RL 分界，以及唯一 X 的位置；两侧是否合法可由前后缀常数时间判断。若中心原值已确定，只需检查它不等于相邻下标；若为 $-1$，中心在端点有 $N-1$ 种选择，在内部有 $N-2$ 种选择（$N=1$ 时为 $1$ 种）。累加所有互不相交的结构即可。

复杂度

时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。