題意 ：

• 給一個(gè)結(jié)點(diǎn)1-n的樹(shù)，E先手，將棋子放在其中一個(gè)結(jié)點(diǎn)上，S后手，棋子每次移動(dòng)有三個(gè)條件要滿足：1.結(jié)點(diǎn)相鄰；2.結(jié)點(diǎn)未被訪問(wèn)；3.$u\oplus v\le min(u,v)$。無(wú)法移動(dòng)的人輸。現(xiàn)在重排列這些結(jié)點(diǎn)的編號(hào)，要求E第一次下時(shí)就能保證E贏的結(jié)點(diǎn)數(shù)最多，輸出一種重排列方案

思路 ：

• 大膽猜想，如果每一個(gè)點(diǎn)都無(wú)法走到其他點(diǎn)，即每一個(gè)點(diǎn)都是孤立的，那么E無(wú)論從哪個(gè)點(diǎn)出發(fā)都是必勝的，第一次下時(shí)就能保證E贏的結(jié)點(diǎn)數(shù)必然是最大的
• 結(jié)論 ：一棵樹(shù)一定是一個(gè)二分圖（可以黑白染色）
• 我們的構(gòu)造方案要滿足$?(u,v)\in E,u$ $xor$ $v>min(u,v)$，不妨設(shè)$u>v$，考慮𝑢的二進(jìn)制的最高位，不難發(fā)現(xiàn)原條件等價(jià)于在這一位上𝑣只能為0，即相鄰的兩個(gè)結(jié)點(diǎn)必須要滿足最高位不同，即在二進(jìn)制下的位數(shù)不同
• 相鄰結(jié)點(diǎn)之間不能到達(dá)（想到二分圖），這種相鄰結(jié)點(diǎn)之間有不同屬性的問(wèn)題可以從黑白染色法考慮，相鄰結(jié)點(diǎn)染不同顏色
• 設(shè)白色有w個(gè)，黑色有b個(gè)，且不失一般性地令$w\le b$，我們可以將這n個(gè)數(shù)分為個(gè)數(shù)為w和b的兩個(gè)集合，要滿足二進(jìn)制下位數(shù)相同的被放在同一個(gè)集合中
• 最高有效位是第0位的有$2^0$個(gè)，最高有效位是第1位的有$2^1$個(gè)…，因此，可以按二進(jìn)制的最高位將標(biāo)號(hào)1-n分為$logn$組，最高有效位是第i位的記為第$label$_$grou{p}_i$
• 在原圖上跑dfs染色法能得到二分圖的兩個(gè)分量，然后看如何分配標(biāo)號(hào)的分組，取大小較小的一個(gè)分量，它的結(jié)點(diǎn)可以拆成多個(gè)$2^i$大小的組，大小為$2^i$的組剛好和$label$_$grou{p}_i$對(duì)應(yīng)（恰好構(gòu)成二進(jìn)制拆分），然后再把剩下的標(biāo)號(hào)分配給另外一個(gè)分量的結(jié)點(diǎn)
• 二進(jìn)制拆分 ：一個(gè)數(shù)一定可以被分為若干個(gè)$2^i$相加

#include <iostream> #include <vector>using namespace std;const int N = 2e5 + 10;int n; vector<int> g[N]; int sum0, sum1; int col[N], f[N], ans[N];void dfs(int u, int fa, int c) {col[u] = c;if (c) sum1 ++ ;else sum0 ++ ;for (int i = 0, v; i < g[u].size(); i ++ ){v = g[u][i];if (v == fa) continue;dfs(v, u, c ^ 1);} }int main() {int _ = 1;scanf("%d", &_);while (_ -- ){scanf("%d", &n);for (int i = 1; i <= n; i ++ ) g[i].clear();for (int i = 0, u, v; i < n - 1; i ++ ){scanf("%d%d", &u, &v);g[u].push_back(v), g[v].push_back(u);}sum0 = sum1 = 0;dfs(1, 0, 0); // 在原圖上跑// 找較小的集合，且改變顏色，始終使較小的那個(gè)集合顏色為0if (sum0 > sum1){swap(sum0, sum1);for (int i = 1; i <= n; i ++ ) col[i] ^= 1;}for (int i = 1; i <= n; i ++ ){int hb; // 1-n分別在二進(jìn)制下的最高有效位for (hb = 30; hb >= 0; hb -- )if (i >> hb & 1)break;// 較小的那個(gè)集合被分為若干個(gè)大小為2^i的組if (sum0 >> hb & 1) f[i] = 0; // 較小的那個(gè)集合的二進(jìn)制表示在它的最高有效位是1，那么它應(yīng)該被分到這個(gè)較小的集合else f[i] = 1; // 剩余的都是較大的那個(gè)集合}int cnt0 = 1, cnt1 = 1; // 從1開(kāi)始for (int i = 1; i <= n; i ++ ){if (col[i] == 0) // 這個(gè)結(jié)點(diǎn)是較小集合的顏色{while (f[cnt0] == 1) cnt0 ++ ; // 找到cnt0使得f[cnt0] == 0ans[i] = cnt0 ++ ; // 在這個(gè)原圖的結(jié)點(diǎn)上放上應(yīng)當(dāng)放的顏色的第順序個(gè)}else{while(f[cnt1] == 0) cnt1 ++ ;ans[i] = cnt1 ++ ;}}for (int i = 1; i <= n; i ++ ) printf("%d ", ans[i]);puts("");}return 0; } 與50位技術(shù)專(zhuān)家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的Treelabeling 异或性质，位运算，染色法，二分图（2100）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。