链接

Tree Constructer

思路

题意是这样的:给一个可重集，其中任意两个元素的或和（即 x | y）若为 \(2^{60}-1\) 则在它们之间连一条无向边。给出一棵树，让你构造一个集合使其对应的图就是这棵树。

稍微模拟几种情况可以发现，同一层的点存在某种关系，相邻两层的点之间也存在某种关系，而树又必然是二分图，可以利用二分图的性质去构造。

先 DFS 一遍给所有点分类，选择点数不大于一半的一边为左边，然后用两位来标识：左边都是 01 右边都是 10，这样同一边的点之间就连不上边。对于左边的点，按顺序将其对应的那一位的 1 去掉，只有和他相连的右边的点这一位才取 1。由于之前左边的点数不超过一半，这里最多需要 \(50\) 位，不会出现问题。

代码

vi l, r, g[maxn];
int color[maxn];
ll ans[maxn];
int n, pos[maxn];
void dfs (int now, int fa, bool col)
{
    if (col) l.pb (now);
    else r.pb (now);
    color[now] = col;
    for (auto i : g[now]) if (i != fa) {
        dfs (i, now, !col);
    }
}
signed main ( )
{
    cin >> n;
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        g[u].pb (v), g[v].pb (u);
    }
    dfs (1, 0, 1);
    if (l.size ( ) > r.size ( )) swap (l, r);
    ll tmp = (1LL << 60) - 1;
    fill (ans + 1, ans + n + 1, tmp);
    for (auto i : l) ans[i] ^= (1LL << 55);
    for (auto i : r) {
        ans[i] ^= ((1LL << 50) - 1);
        ans[i] ^= (2LL << 55);
    }
    for (int i = 0; i < l.size ( ); ++i) {
        ans[l[i]] ^= (1LL << i);
        for (auto j : g[l[i]]) {
            ans[j] |= (1LL << i);
        }
        pos[l[i]] = i;
    }
    for (int i = 1; i <= n; ++i)
        cout << ans[i] << (i == n ? endl : ' ');
    return 0;
}