CF1605D Treelabeling 题解

$u\oplus v\le\min(u,v)$ 十分的别扭，于是考虑转换条件。令 $l$ 表示 $u,v$ 二进制最高的 $1$ 位的最大值，则显然若 $u,v$ 在第 $l$ 位上的值相同，则等式成立，否则等式不成立。

因此可以发现，若 $\exist i,s.t.u,v\in[2^i,2^{i+1})$，则 $u,v$ 两个点满足条件，否则不满足条件。因此给 $[2^i,2^{i+1})$ 段内所有元素定义为 $i$ 色。

因为树是二分图，所以考虑给树黑白染色，要求树上相邻两个结点的色必须不同。这是容易构造的，二进制拆分一下即可。于是做完了。

代码。