NK52189J

数位dp稍微有难度的题

NK52185J Tree Constructer

题意

n个点的树，每个点分配$[0,1<<60)$的点权，如果u与v的点权进行按位或之后等于$2^{60}-1$那么有边，否则没边。求合法的点权序列构造出给定的树。

分析

黑白染色之后构造分类方式

读题之后发现，如果有某一位两个点都是0那么这两个点必定没有边，通过这个性质，对这个树进行黑白染色。
黑白染色之后，同色点之间必定没有边，那么使用两位二进制就可以把同色点全部分开。然后还剩下一些边为不相邻的黑白点之间的边，因为黑色点和白色点总和为n，那么必定有一种颜色的点的个数$\le \frac{1}{2}$对于点数较小的集合，按照标号依次分配二进制位为0。对于另一个颜色的集合，其在分配的二进制位中只有与其相邻的异色点对应编号的二进制位位1，其他均为0。

代码

//
// Created by mrx on 2023/2/27.
//
#include <functional>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <cmath>
#include <queue>
#include <array>
#include <map>

using i64 = long long;

void solve() {
    int n;

    std::cin >> n;
    std::vector adj(n, std::vector<int>());
    for (int i = 1; i < n; ++i) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    std::vector<std::vector<int>> cl(2);
    std::vector<int> color(n);
    std::function<void(int, int, int)> dfs = [&](int u, int p, int c) {
        cl[c].emplace_back(u);
        color[u] = c;
        for (auto x: adj[u]) {
            if (x == p)continue;
            dfs(x, u, c ^ 1);
        }
    };
    dfs(0, 0, 0);
    if (cl[0].size() > cl[1].size())std::swap(cl[0], cl[1]);
    std::vector<i64> ans(n, (1ll << 60) - (1ll << cl[0].size()));
    std::vector<int> pos(n, -1);
    for (int i = 0; i < cl[0].size(); ++i)pos[cl[0][i]] = i;
    for (auto x: cl[0])ans[x] ^= 1ll << 59, ans[x] ^= ((1ll << cl[0].size()) - 1) ^ 1ll << pos[x];
    for (auto x: cl[1])ans[x] ^= 1ll << 58;
    for (auto x: cl[1])for (auto v: adj[x])ans[x] ^= 1ll << pos[v];

//    for (int i = 0; i < n; ++i) {
//        for (int j = i + 1; j < n; ++j) {
//            if ((ans[i] | ans[j]) == (1ll << 60) - 1)std::cout << i + 1 << ' ' << j + 1 << '\n';
//        }
//    }
    for (auto x: ans)std::cout << x << ' ';
}


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    solve();
    return 0;
}