今天我們來看看CF1141G 題目連結
題目描述
給定一棵包含 $n$ 個城市和 $n-1$ 條道路的樹，要求為每條道路分配一家公司（即染色），使得：
- 不滿足條件的城市：若某城市相鄰的道路中有「兩條或以上」由同一家公司施工，則該城市被認為是不滿足條件的（bad）。
- 整棵樹中，不滿足條件的城市數量至多為 $k$。
目標是最小化所使用的不同公司（顏色）的數量，並輸出一個合法的分配方案
輸入格式
- 第一行包含兩個整數：$n$ 與 $k$。
- 接下來 $n-1$ 行，每行包含兩個整數，表示連接兩個城市的道路。
輸出格式
- 第一行輸出所需的最少公司數量（即顏色數）。
- 第二行輸出 $n-1$ 個數字，表示每條道路分配的公司（顏色），順序與輸入順序一致。
前言
沒想到這題我居然自己想出來，而且和官方解答不一樣，想法更簡單
想法
先說我自己的想法：
稍微想一下可以發現，我們不可能找不到一個$r$使得著色是可能的。因為假設最大的vertex的度數是$D$，那麼給我們$D$個顏色，我們只要從任意一個vertex開始給邊著色，如果發現當前的vertex某個邊已經被著了某個顏色$i$，那我們只要從$i+1$再開始嘗試著色就好，
這實際上可以用Kőnig邊著色定理來解釋(我個人是覺得不用這麼麻煩啦)
任一二分圖均可用正好等於其最大頂點度$D$種顏色，對所有邊進行著色，使得每個頂點所連接的邊都具有互不相同的顏色。
而樹就是一個二分圖，因此可以用正好$D$個顏色著色。
或者，更不失一般性的，我們可以用Vizing定理：
對於任一簡單圖（即無平行邊與自環的圖），圖的邊著色數要麼正好為最大度$D$，要麼為$D+1$。
那麼接下來就很簡單了，我們先對$[1,2,…,n]$這些城市編號排序，由度數最大排到最小。
接著選前$k$個度數最大的，這些我們設定他們為「可以是Bad」的城市。
然後再從任意一點$v$開始dfs，然後開始從$1$開始著色。注意到，因為這張圖是一棵樹，我們進到一個節點的時候只有可能從父節點那邊連過來一個塗過色的邊，所以我們對這個點$v$的邊著色的時候只需要確保顏色不要和父節點一樣就好。
最後，只要看過所有節點，確保最大的顏色是多少，輸出所有邊的顏色即可。
我其實真的不清楚為什麼解答對於先知道有幾種顏色可以用這麼執著，如果你不確定要用剛好$D$個顏色著色的話(不管那些Bad城市的話)，有解法是二分搜。
我一開始也是想說要二分搜，可是寫完dfs以後發現根本就已經把要幾種顏色確定下來了。
程式碼:
const int _n = 2e5 + 10;
int t, n, k, id[_n], T = 0, color[_n];
bool canBeNotGood[_n];
struct E {
int v, num;
};
vector<E> G[_n];
void dfs(int v) {
id[v] = ++T;
int colorToDraw = 1;
int faColor = 0;
rep(i, 0, SZ(G[v])) {
if (id[G[v][i].v]) {
faColor = color[G[v][i].num];
}
}
rep(i, 0, SZ(G[v])) {
if (!id[G[v][i].v]) {
if (canBeNotGood[v]) {
color[G[v][i].num] = 1;
} else {
if (colorToDraw == faColor) colorToDraw++;
color[G[v][i].num] = colorToDraw;
colorToDraw++;
}
dfs(G[v][i].v);
}
}
}
main(void) {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
rep(i, 0, n - 1) {
int x, y;
cin >> x >> y;
x--, y--;
G[x].pb({y, i});
G[y].pb({x, i});
}
vector<int> cities;
rep(i, 0, n) cities.pb(i);
sort(all(cities), [](int& lhs, int& rhs) {
return G[lhs].size() > G[rhs].size();
});
rep(i, 0, k) {
canBeNotGood[cities[i]] = 1;
}
dfs(0);
int ansR = 0;
rep(i, 0, n - 1) {
ansR = max(ansR, color[i]);
}
cout << ansR << '\n';
rep(i, 0, n - 1) {
cout << color[i] << ' ';
}
cout << '\n';
return 0;
}
標頭、模板請點Submission看 Submission