CF2040D Non Prime Tree

Tag：思维、构造

题目描述

给你一棵拥有 \(n\) 个顶点的树。

你的任务是构造一个包含 \(n\) 个不同整数的数组，这些整数从 \(1\) 到 \(2 \cdot n\) 分别取值。同时要求对于树中的任意一条边 \(u_i \leftrightarrow v_i\)，对应的数组元素差值 \(|a_{u_i} - a_{v_i}|\) 不是质数。

请你找出任意一个符合以上条件的数组，如果不存在这样的数组，请输出 \(-1\)。

数据说明：

\(2 \le n \le 2 \cdot 10^5\)

分析

我们考虑对这棵树进行 \(\text{DFS}\)，在 \(\text{DFS}\) 的过程中维护一个 \(cnt\)，初始为1。

每当我们 \(\text{DFS}\) 到一个点的时候，我们先判断当前 \(cnt\) 与其父亲的答案差值是否为 \(1\)，如果差值为 \(1\) 我们可以很自然地把 \(cnt\) 填到这个位置。当我们反复填到树上的某一叶子时，我们需要回头去填之前某一个结点的另一个子树，这个时候 \(cnt\) 与父亲节点的答案差值不可能为 \(1\)，我们就判断 \(cnt\) 与父亲节点的差值是否为一个不为 \(2\) 偶数就可以了，如果是一个奇数，我们就直接 \(cnt\) 加一，让其成为一个偶数，如果为 \(2\) 我们会把 \(2\) 变成 \(4\)。

代码实现

void NeverSayNever() {
    int n;
    cin >> n;
    vector<vector<int> > adj(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        u--,v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int cnt = 1;
    vector<int> ans(n);
    auto dfs = [&](auto &&self, int cur, int fa) -> void {
        while (cnt - ans[fa] != 1 && ((cnt - ans[fa]) & 1 || (cnt - ans[fa] == 2))) cnt++;
        ans[cur] = cnt++;
        for (auto &nxt: adj[cur]) {
            if (nxt == fa) continue;
            self(self, nxt, cur);
        }
    };
    dfs(dfs, 0, 0);
    for (int i = 0; i < n; i++) {
        cout << ans[i] << " ";
    }
    cout << endl;
}

日志

本页面创建于 2024/02/16 13:19