CF1819C / 膜拜柠檬姐姐

· · 题解

前言

柠檬姐姐 在语文课课前三分钟演讲讲的神题/bx，一定要补完！

题解

先考虑一个很 simple 的情况，即树退化成了一条链的形式。

对链按照下表奇偶染色，尽量跳 2 的长度，如果 n\bmod 2=1 那么特殊判断一下，第一步跳 1 的长度即可。

然后考虑本题。

Lemma 1：一棵树可以被这样染色，当且仅当这棵树是一个毛毛虫树。

如果图不是毛毛虫树，那么就至少存在一条长度为 2 的非直径链挂在直径的中间。

容易证明如果选择从距离直径远的点跳到距离直径近的点，那么直径就必然存在连续的两个点被染色，回去的时候就会不存在这样长度的点。反过来，就无法从直径远的点跳回到直径上的点。画图即可发现。

问题就是怎么在毛毛虫树构造一组合法的方案。

从树上任意一条直径的任意一个端点开始执行程序，优先走距离为 2 的树上没有被走过的直径距离 1 的节点的叶子节点，其次走树的直径上距离为 2 的点，最后再走剩下距离的点回来即可。

时间复杂度是 O(n) 的。

描述很不优美，建议参考代码。

代码

// lemon sister shines, thanks lemon sister!
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e5 + 10;
int n;
vector<int> z[N], res;
bool vis[N];
int dis[N];

bool cap() {
    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        for (auto &j : z[i]) {
            if (z[j].size() != 1) {
                cnt++;
            }
        }
        if (cnt > 2) {
            return false;
        }
    }
    return true;
}

void bfs() {
    queue<int> q;
    q.push(1);
    vis[1] = false;
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    while (q.size()) {
        int f = q.front();
        q.pop();
        vis[f] = false;
        for (auto &g : z[f]) {
            if (dis[g] > dis[f] + 1) {
                dis[g] = dis[f] + 1;
                if (!vis[g]) {
                    vis[g] = true;
                    q.push(g);
                }
            }
        }
    }
}

void dfs(int u, int fa) {
    vector<int> foot;
    for (auto &v : z[u]) {
        if (v != fa) {
            if (z[v].size() > 1) {
                // 直径上的节点
                for (auto &w : z[v]) {
                    if (w != u) {
                        if (z[w].size() == 1) {
                            res.push_back(w);
                        }
                    }
                }
                for (auto &w : z[v]) {
                    if (w != u) {
                        if (z[w].size() > 1) {
                            res.push_back(w);
                            dfs(w, v);
                        }
                    }
                }
                res.push_back(v);
            } else {
                // 毛毛虫脚上的节点
                foot.push_back(v);
            }
        }
    }
    for (auto &x : foot) {
        res.push_back(x);
    }
}

signed main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        z[x].push_back(y);
        z[y].push_back(x);
    }
    if (cap()) {
        cout << "Yes\n";
        bfs();
        int best = max_element(dis + 1, dis + n + 1) - dis;
        res.push_back(best);
        // best 是毛毛虫直径的一端点
        dfs(best, 0);
        for (auto &x : res) {
            cout << x << ' ';
        }
        cout << '\n';
    } else {
        cout << "No\n";
    }
}

总结

在语文课上讲 OI 的柠檬姐姐好闪，拜谢柠檬姐姐！