题解：CF2065F Skibidus and Slay

结论题。

看完题目觉得十分困难，难道是树剖？但这是 Div.4，不会太困难，直接大胆猜测：对于一条路径不需要全部遍历，只需要找一部分。

那要找的长度到底是多少？考虑一条合法的路径的性质。

用 $1$ 表示多数元素，$0$ 表示非多数元素，因为 $1$ 出现了总数的一半以上，所以有很大概率会有 $2$ 个甚至更多的 $1$ 在一起，最差情况也会是 $1$ 和 $0$ 交替出现。换而言之，合法路径必然包含 $1,1$ 或 $1,0,1$ 类型的子序列。

设路径长度为 $n$，更详细的说：

若 $n$ 为奇数（这部分来源于官解），设其中有 $k$ 个 $1$，$n-k$ 个 $0$，已知 $k>n-k$，那么 $2k>n$，若不包含 $1,1$，那么每个 $1$ 之间都需要 $0$，所以 $n-k\ge k-1$，可得 $2k \le n+1$。综合可得 $n<2k \le n+1$，则 $k$ 唯一取值为 $\frac{n+1}{2}$，此时路径为 $1,0,1,0...$，包含 $1,0,1$。

若 $n$ 为偶数，则 $1$ 出现至少 $n\div 2+1$ 次，但不重叠的长度为 $2$ 的段只有 $n\div 2$ 个，根据抽屉原理，必然有至少一段出现 $2$ 个 $1$，也就是出现 $1,1$。

综上，可以得到一个一般结论：若存在一条多数元素为 $i$ 的路径，则必然存在两个相邻节点的数都为 $i$，或一条长度为 $3$ 的路径，其两端的数为 $i$。

然后就可以枚举着找了，判断数字可以用 map，具体可以看官解或别的题解，这里不放代码了。