题解：AT_agc058_c [AGC058C] Planar Tree

眼前一亮思维题。

看过 CEFqwq 写黑色思维题题解的真爱粉应该都知道 CEF 喜欢列举公理及推论，这篇题解也不例外。

下面记 d(x,y) 表示 x 号点到 y 号点的距离。下文优弧和劣弧可能长度相等，不影响推导。

公理 1

我们不妨假设环是一个圆，连接 x 和 y 的弦和连接 x-k_1 与 y+k_2（x+k_1 和 y+k_2 不在 x 和 y 所在的劣弧上）的弦不交。

（没学过初中几何的同学可以查阅资料 qwq。）

公理 2

一个点出发向两个不同点连边，所得两条弦交于圆上。

推论 1

若两个相邻点权值相同，只保留其中一个点，不影响正确性。

证明：假设两点分别为 x 与 x+1，从点 y 向 x 连边，分出一条优弧，一条劣弧。

• 若 d(x,y) > d(x+1,y)。若 y 向 x+1 连一条边，优弧上的点依旧只能连优弧上的点或者是 x,x+1,y，且无论一个点连 x 还是 x+1 都不会改变和其余弦的相交关系，劣弧上的点同理。没有影响。

• 若 d(x,y) < d(x+1,y)。同理。我们会发现两种情况只改变我们在原先基础上多选择的点是在优弧上还是劣弧上。

如果三个点连续，连了之后只有一条弧怎么办？这个时候连边对其余点没有任何影响。

概括一下就是，缩成一个点之后优弧上的点和劣弧上的点依旧可以连接 x 和 x+1，只不过本来两条弧分别连两个点，缩完之后变成了连一个点（好像是废话）。

推论 2

若相邻两个点为 1,2 或者 3,4，可以不保留 1 或 4，留到后续处理。

证明：1 只能和 2 连，3 只能和 4 连。2 可以连 3 或 1 然后再连到 2，而 2 如果要在生成树中，必须连一个 1 或 3，或者让 1 再连另一个 2。具体可以看看后面如何处理这一部分。

我们先把相邻的 2,3 和 1,4 这个问题搁置，接下来我们考虑剩下的 1 和 4 如何处理，仔细分析可以发现，如果每个 2 和 3 只匹配一个 1 和一个 4，一定存在方案使得弦两两不交于圆内，否则不存在。

于是我们可以把剩下的 1 和 4 匹配掉。最后我们处理是否有剩下的 3 和 2 可以把图连起来。前面把一些 1 和 4 并入了 2 和 3 中，在这一步我们把 2 和 3 连起来就处理掉了。

我们不妨开一个 vector 维护相邻，最后用桶统计。

#include<bits/stdc++.h>
using namespace std;
int lsh[] = {0, 2, 2, 3, 3}, t, n, buk[5];
vector<int> a;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> t;
    while (t--){
        cin >> n;
        a.clear();
        for (int i = 1; i <= n; i++){
            int x;
            cin >> x;
            if (!a.empty() && lsh[x] == lsh[a.back()]){
                if (lsh[x] == x)
                    a.back() = x;
            }else
                a.push_back(x);
        }
        if (lsh[a[0]] == lsh[a.back()]){
            if (lsh[a[0]] != a[0]){
                a[0] = a.back();
                a.pop_back();
            }else
                a.pop_back();
        }
        buk[1] = buk[2] = buk[3] = buk[4] = 0;
        for (auto x : a)
            buk[x]++;
        if (buk[1] >= buk[3] || buk[4] >= buk[2])
            cout << "No\n";
        else
            cout << "Yes\n";
    }
    return 0;
}