题目描述

现在给定描述，如果两个点之间的或运算结果答案是 $2^{60}-1$ ，说明这两个点之间有边。
问给你一个n个节点，你如何设置节点值，使得构造出来的图是一棵树，题目给出数的边信息。

$n\leq 100$ ，输出构造的节点值 $0\leq a_i\leq2^{60}-1$ 。

Solution

数据范围的n很小，并且答案给的是一个关于 $2$ 的幂次的形式，那么就要往二进制方向靠。
这也是一个比较新奇的思维题了吧，如果当时脑子没想明白可能很难写出来，想明白了或者见过类似的就会很容易。
我们首先根据题目给出的树边信息，进行二分图的黑白染色。把树中全部节点分为黑白两种节点。
那么我们在假设白节点数小于黑节点数的前提下。进行下面的分配操作。
对全部的白色节点进行编号，使得这些白色节点的权值二进制表示中它的编号位是 $0$ ，以及最高位也就是 $59$ 位是 $0$ 。
全部黑色节点，只把它的二进制表示位第 $59$ 位置为 $1$ ，其余的，和它相邻的白点编号的二进制对应位置都置为 $1$ 。

进行上面操作之后你就得到了答案。现在我们想想为什么这样就会符合要求。
第一步我们先看对白色节点的分配操作，全部的白色节点最高位也就是 $59$ 位都不是 $1$ ，以及对应编号位也不是 $1$ ，说明任意两个白色节点之间都不会存在边。
第二步我们看黑色节点的分配操作，它把最高位设置成了 $1$ ，也把和它相邻的编号位都设置成了 $1$ ，这样说明和它相邻的白点都有到对应的边，不和它相邻的白点，因为编号不一致，导致二进制位不同为 $1$ ，一定不会有和它连边的情况。
第三步我们看为什么要使得白色节点数小于黑色节点数。如果不考虑先白还是先黑染色，很容易构造出一个菊花图，假设第一个节点是黑的，那么它的全部孩子都是白的，最多有 $99$ 个白节点，但是我最高的二进制位只有 $59$ 并且还不能标编号，所以我们最多只能支持有 $58$ 个白色编号，因为数的结构特性，我们一定有一种颜色是小于 $50$ 的，那么只要找到染色方案，使得白色数量不要超过 $50$ 即可。并且这里也解释了为什么黑点之间一定不会有边，如果我们要让黑点之间存在一条边，说明一定有两个黑点他们链接的白点之间数量大于 $58$ 个，才可能存在一条边，但是这样的黑点存在吗，看看我们上面使得白节点数一定小于黑节点数这个要求，如果白节点有了 $58$ 个，在最多 $100$ 个节点的树中，这是不存在的情况。所以这个问题也就得到了解决。

这个思维题关键在于转换二分染色，以及边权关系如何处理，还要保证某个特定的颜色满足一定的需求，例用题目给出的数据范围，确定我们的做法是正确的。）当然确定正确这个东西如果在赛场上，如果没什么好的别的想法就先 $WA$ 一发再说，指不定就 $AC$ 了呢。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 100 + 7;

ll n, m;
int head[N], tot;
struct Node {
    int v, nxt;
}edge[N << 1];
void add(int u, int v) {
    edge[++tot].v = v;
    edge[tot].nxt = head[u];
    head[u] = tot;
}

int id[N];
ll ans[N];
vector<int> color[2];

void dfs(int u, int fa, int col) { // 黑白染色
    color[col].push_back(u);
    for (int i = head[u]; i; i = edge[i].nxt) {
        int v = edge[i].v;
        if (v == fa)    continue;
        dfs(v, u, col ^ 1);
    }
}

void solve() {
    n = read();
    rep(i, 1, n - 1) {
        int u = read(), v = read();
        add(u, v), add(v, u);
    }
    dfs(1, -1, 0);
    if (color[0].size() > color[1].size())
        swap(color[0], color[1]); // 白点选择少的哪一些
    int cnt = 0;
    ll bs[70];
    rep(i, 0, 62)    bs[i] = 1ll << i; // 写一堆位运算比较麻烦
    for (auto& it : color[0]) { // 白点
        ans[it] = bs[60] - 1 - bs[59] - bs[cnt];
        id[it] = cnt++;
    }
    for (auto& it : color[1]) { // 黑点
        ll tmp = 0;
        for (int i = head[it]; i; i = edge[i].nxt) {
            int v = edge[i].v;
            tmp |= bs[id[v]];
        }
        ans[it] = bs[59] + tmp;
    }
    rep(i, 1, n)    print(ans[i], 32);
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}

【每日一题】2月1日Tree Constructer 思维题，树结构

题目描述

Solution