8.8趣题杂题学习笔记

AGC058C Planar Tree

题意：

有 \(T\) 组数据 \(T(T \leq 75000)\)。

每组数据输入一个环，环上的点的个数为 \(n(n \leq 300000)\)，并且环上每个点有一个权值 \(A_i \in \{1,2,3,4\}\)，保证每种权值都至少出现一次。环上两个点 \(i, j\) 之间能连边当且仅当 \(|A_i - A_j| = 1\)。

问是否可能连上 \(n-1\) 条边后形成一棵树，且树上每条边不在非端点处相交。

题解：