场上不会 t2 会了这个（挠头

题面就是给定一张无向图，每个点有一个颜色，还给定一个长度为 $k$ 的颜色序列 $b$，对于每个节点求这个序列的最长后缀的起始位置（下标从 $0$ 开始）使得这个先手在这个后缀上玩以下游戏必胜，没有的话输出 $-1$：

• 一开始有一个棋子在当前起点上，先后手在序列上轮流移动，每次需要到达一个当前节点能到达的节点（至少移动一条边）使得到达的节点的颜色和当前序列上考虑的颜色相等。第一个不能满足这个要求的人输。如果最后一个操作的人完成了最后一次操作，那么这个人赢。

$n,k \leq 10^6,m\leq 2.2\times 10^6$

特殊性质 A：图是 DAG

特殊性质 B：$b_i=i$

Sub 1,2

首先缩点，然后考虑朴素的 DP：$dp_{u,i}$ 表示以 $u$ 这个分量为起点，$i$ 开头的后缀中先手是否必胜。对于转移，枚举先手选的第一个点在哪个连通分量。

在 $u$ 的话需要满足 $size_u>1$（因为要至少一个）并且 $u$ 内有 $b_i$ 这个颜色。此时若 $dp_{u,i+1}=0$ 则 $dp_{u,i}\leftarrow 1$。

在 $u$ 的某个后继 $v$ 的话需要满足其中有 $b_i$ 这个颜色。此时若 $dp_{v,i+1}=0$ 则 $dp_{u,i}\leftarrow 1$。

否则在更远的连通分量的话就让 $dp_{u,i}$ 或上所有 $dp_{v,i}$。

注意第一种转移要放在最后，因为会用到自身的 $dp$ 值。

复杂度 $O(mk)$。

特殊性质 AB

此时每个分量里只有一种颜色。考虑转换 DP 状态：$dp_u$ 表示 $u$ 这个分量内最小的数 $i$ 满足 $i$ 开头的后缀满足要求（注意原 DP 数组并不单调但是我们依旧可以这样转换，原因是并不影响转移，见下）。

此时上述第三种转移是容易的，$dp_u\leftarrow \min\{dp_u,dp_v\}$ 即可。第一种转移不存在（因为 $size=1$），所以只考虑第二种转移。

此时我们找到当前分量 $v$ 中唯一的颜色 $c$ 在数组中的位置。由于 $b_i=i$ 所以原数组中只有 $c$ 一个位置上面是 $c$。所以在前面的做法中只有 $dp_{v,c}$ 会被转移影响到。讨论 $c$ 的大小：

• $c\geq dp_v$，此时不会影响答案，忽略。
• $c= dp_v-1$，此时由于 $c+1=dp_v$，而由 $dp$ 状态的定义得原来的 $dp_{v,c+1}$ 一定为 $1$，所以无法转移。
• $c\lt dp_v-1$，此时可以转移，因为由于 $c+1\lt dp_v$，而 $dp_v$ 是最小的 $1$ 的位置所以一定为 $0$。

综上，只有 $c\lt dp_v-1$ 的位置可以转移。对于所有的这样的 $c$ 让 $dp_u\leftarrow \min\{dp_u,c\}$ 即可。

复杂度 $O(m)$。

特殊性质 B

此时缩点之后依旧可以枚举每个后继的所有颜色来转移。注意从大往小枚举。

而由于当前分量里 $size$ 可能 $>1$ 所以要带上第一种转移，不过是类似的。

All subs

对于 $b_i\not= i$ 的情况，有可能有些颜色在原数组上有很多位置。此时我们研究从大往小转移的过程。可以发现对于一段连续的 $b$ 数组上的位置 $b[l\dots r]$ 满足这一段中所有数都在 $v$ 中出现过，那么能不能转移用 $0$ 和 $1$ 表示的情况为：$\dots 01010101$，其中 $r$ 的位置上是 $1$。这是因为由于转移的形式无法有连续两个位置参与转移。而不相邻的连续段之间没有联系。

我们发现，对于原数组上出现的最小的位置 $p$，$p$ 和 $p+1$ 至少有一个被用来转移了，我们只需要知道是 $p$ 还是 $p+1$ 即可。这只取决于最小值所在的连续段的长度的奇偶性，所以我们只需要求最小值的值，和这个长度，即可。

前者是好求的。对于后者，我们在原数组 $b$ 上记录 $lst_i$ 表示前一个与 $i$ 位置上的数相同的位置。在求连续段的时候，我们每次向右倍增出第一个 $lst$ 值小于 $p$ 的位置，这也就是下一个还没有出现过的数，如果这个数没出现那么返回这个位置否则就继续这个过程。暴跳的总次数是 $O(n+m)$ 的（因为每个颜色最多被跳了一次），所以总复杂度为 $O((n+m)\log n)$。可以通过。

Bonus

群里有大佬给出了线性求法，但是我忘了。留给读者自行探究（