Hello 2026——D2. Tree Coloring (Hard Version)（随机化算法可以分层实现）（猜测答案时，可以先猜测一个下界然后尝试不断提升） · znzryb
## 题目大意
**问题描述:**
- 给定一棵有 n 个顶点的有根树,**根节点为 1**,所有顶点初始为白色
- 定义 $d_i $ 为**根节点**到**第 i 个顶点**的距离
**操作规则:**
- 每次操作可以选择一个白色顶点的子集 S
- S 中的任意两个节点必须满足:
- 不通过边相连(不相邻)
- 到根节点的距离不相同(不在同一层)
- 将 S 中的所有顶点涂成黑色
**目标:**
- 求将整棵树全部涂成黑色所需的最少操作次数
**数据范围:**
- 测试用例数 t: 1 ≤ t ≤ 10⁴
- 顶点数 n: 2 ≤ n ≤ 2×10⁵
- 所有测试用例的 n 之和不超过 2×10⁵
**版本说明:**
- 这是简化版本,只需要输出最少操作次数
- 困难版本(D2)需要输出具体的操作方案
**启示：当我们发现一道题目需要猜结论，但是我们没啥思路的时候，不妨****先猜下界****，然后想办法****不断提升这个下界****（特别是对于这种个数推断与猜测）。**
## 思路讲解
easy version，我们想要搞一个这个 dp，但是就出现这个问题了，因为和别的子树的交互，删除，没有考虑到，这个是树上 dp 的弱点，要么想办法在这个转移/合并的时候解决这个问题，要么就换做法。
发现这个 easy version 过题比较多，那么就要想到，可能就是猜结论了，不过直接猜出来比较难，我们可以先**猜猜下界**。首先，设 $t_i$ 为第 $i$ 层的节点个数，那么 $ans≥\text{max}(t_1,\cdots,t_n)$ 是肯定的，不过，如果说 $i$ 层的这个所有节点都共用一个根节点，这个时候还需要对 $t_i+1$ 取 max 值。（这个就是 easy 版本的结论）
那么 hard 版本就相当于构造性证明这个结论。
不过，想办法构造比较困难，我们不如交给随机化算法。即，我们的这个构造实际上可以看作为给这个节点涂颜色，要求节点颜色种类不能超过 $ans$，并且和父节点颜色不同。我们仅仅只是使用一个这个 $holeColor$ 的贪心进行一个瞎搞。
```cpp
for (int i=1;i<=mx_dep;++i) {
while (true) {
shuffle(all(dep_node_mtx[i]),rng);
ll holeColor=-1;
ll cur_color=1;
for (auto u:dep_node_mtx[i]) {
if (holeColor!=-1 && holeColor!=color[parent[u]]) {
color[u]=holeColor;
holeColor=-1;
continue;
}
if (cur_color!=color[parent[u]]) {
color[u]=cur_color;
cur_color++;
}else {
holeColor=cur_color;
cur_color++;
color[u]=cur_color;
cur_color++;
}
}
if (cur_color<=ans+1) {
break;
}
}
}
```
## AC代码
::: d1
```cpp
/**
* Problem: D1. Tree Coloring (Easy Version)
* Contest: Hello 2026
* Judge: Codeforces
* URL: https://codeforces.com/contest/2183/problem/D1
* Created: 2026-01-17 19:53:19
* Author: Gospel_rock
*/
#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT;
/*
*
*/
void Solve() {
ll N;
cin >> N;
vector<vector<ll>> g(N+2);
for (int i=1;i<=N-1;++i) {
ll u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<vector<ll>> dep_node_mtx(N+2);
vector<set<ll>> dep_fa_mtx(N+2);
ll mx_dep=0;
auto dfs=[&](auto && self,ll u,ll p,ll dep) -> void {
dep_node_mtx[dep].push_back(u);
dep_fa_mtx[dep].insert(p);
mx_dep=max(mx_dep,dep);
for (auto to:g[u]) {
if (to==p) {
continue;
}
self(self,to,u,dep+1);
}
};
dfs(dfs,1,-1,1);
ll ans=0;
for (int i=1;i<=mx_dep;++i) {
ll ti=SZ(dep_node_mtx[i]);
if (dep_fa_mtx[i].size()<=1) {
ans=max(ans,ti+1);
}else {
ans=max(ans,ti);
}
}
cout<<ans<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> lT;
while(lT--)
Solve();
return 0;
}
/*
*/
```
:::
AC
[https://codeforces.com/contest/2183/submission/358257705](https://codeforces.com/contest/2183/submission/358257705)
::: d2
```cpp
/**
* Problem: D2. Tree Coloring (Hard Version)
* Contest: Hello 2026
* Judge: Codeforces
* URL: https://codeforces.com/contest/2183/problem/D2
* Created: 2026-01-17 20:14:41
* Author: Gospel_rock
*/
#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT;
/*
*
*/
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void Solve() {
ll N;
cin >> N;
vector<vector<ll>> g(N+2);
for (int i=1;i<=N-1;++i) {
ll u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<vector<ll>> dep_node_mtx(N+2);
vector<set<ll>> dep_fa_mtx(N+2);
vector<ll> parent(N+2);
ll mx_dep=0;
auto dfs=[&](auto && self,ll u,ll p,ll dep) -> void {
parent[u]=p;
dep_node_mtx[dep].push_back(u);
dep_fa_mtx[dep].insert(p);
mx_dep=max(mx_dep,dep);
for (auto to:g[u]) {
if (to==p) {
continue;
}
self(self,to,u,dep+1);
}
};
dfs(dfs,1,0,1);
ll ans=0;
vector<ll> color(N+2);
for (int i=1;i<=mx_dep;++i) {
ll ti=SZ(dep_node_mtx[i]);
if (dep_fa_mtx[i].size()<=1) {
ans=max(ans,ti+1);
}else {
ans=max(ans,ti);
}
}
vector<vector<ll>> op_mtx(ans+2);
for (int i=1;i<=mx_dep;++i) {
while (true) {
shuffle(all(dep_node_mtx[i]),rng);
ll holeColor=-1;
ll cur_color=1;
for (auto u:dep_node_mtx[i]) {
if (holeColor!=-1 && holeColor!=color[parent[u]]) {
color[u]=holeColor;
holeColor=-1;
continue;
}
if (cur_color!=color[parent[u]]) {
color[u]=cur_color;
cur_color++;
}else {
holeColor=cur_color;
cur_color++;
color[u]=cur_color;
cur_color++;
}
}
if (cur_color<=ans+1) {
break;
}
}
}
cout<<ans<<"\n";
for (int i=1;i<=N;++i) {
op_mtx[color[i]].push_back(i);
}
for (int i=1;i<=ans;++i) {
cout<<SZ(op_mtx[i])<<" ";
for (auto u:op_mtx[i]) {
cout<<u<<" ";
}
cout<<"\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> lT;
while(lT--)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2183/submission/358257705
*/
```
:::
## 心路历程（WA，TLE，MLE……）
走了一些弯路，**做这种图论的题目，还是需要更有整体意识**
::: 源代码
```cpp
/**
* Problem: D1. Tree Coloring (Easy Version)
* Contest: Hello 2026
* Judge: Codeforces
* URL: https://codeforces.com/contest/2183/problem/D1
* Created: 2026-01-17 15:49:35
* Author: Gospel_rock
*/
#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT;
/*
*
*/
// struct Dep_node {
// ll dep,node;
// };
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void Solve() {
ll N;
cin >> N;
vector<vector<ll>> g(N+2);
for (int i=1;i<=N-1;++i) {
ll u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i=1;i<=N;++i) {
sort(all(g[i]));
}
vector<vector<ll>> dep_node_mtx(N+2);
ll mx_dep=0;
auto dfs=[&](auto && self,ll u,ll p,ll dep) -> void {
dep_node_mtx[dep].push_back(u);
mx_dep=max(mx_dep,dep);
for (auto to:g[u]) {
if (to==p) {
continue;
}
self(self,to,u,dep+1);
}
};
dfs(dfs,1,-1,1);
// 我们每次都先选这个入度最大的点，因此我们先对这个入度大的点进行这个排序
for (int i=1;i<=N;++i) {
shuffle(all(dep_node_mtx[i]),rng);
stable_sort(all(dep_node_mtx[i]),[&](const ll &a,const ll &b) {
return SZ(g[a])<SZ(g[b]);
});
}
ll processed_node=0;
auto check_is_connect=[&](ll u,ll v) {
if (binary_search(all(g[u]),v)) {
return true;
}
return false;
};
ll ans=0;
while (processed_node<N) {
vector<ll> del_node_ls;
for (int i=1;i<=mx_dep;++i) {
if (dep_node_mtx[i].empty()) {
continue;
}
ll u=0;
if (!del_node_ls.empty()) u=del_node_ls.back();
for (int j=SZ(dep_node_mtx[i])-1;j>=0;--j) {
ll v=dep_node_mtx[i][j];
if (!check_is_connect(v,u)) {
dep_node_mtx[i].erase(dep_node_mtx[i].begin()+j);
del_node_ls.push_back(v);
break;
}
}
}
++ans;
processed_node+=SZ(del_node_ls);
}
cout<<ans<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> lT;
while(lT--)
Solve();
return 0;
}
/*
*/
```
:::
顺序会影响结果的原因很朴素：**这段构造是“局部贪心”，它不会为后面的点“预留”某个关键编号**。
同一层里每个点只禁用 1 个编号（父亲的 `du[parent]`），但“哪个点拿走哪个编号”是有讲究的；你现在这套贪心只维护 **一个洞** **`g`**，一旦把洞用在了“本来很灵活的点”身上，就可能把后面那个“更挑剔的点”逼到只能用更大的编号，最后 `> ans` 失败。
我用一个最小反例把它讲清楚（这就是“为什么顺序影响结果”的精髓）：
---
## 反例：明明有解，但某个顺序会让贪心爆掉
设这一层有 3 个点 (A,B,C)，D1 算出来最优 (K=ans=3)。
它们父亲的编号分别是：
- (du[parent(A)] = 1) ⇒ (A) 不能用 1
- (du[parent(B)] = 2) ⇒ (B) 不能用 2
- (du[parent(C)] = 3) ⇒ (C) 不能用 3
显然存在合法分配（且都在 1..3 内）：
$du[A]=2,\ du[B]=3,\ du[C]=1$
都互不相同，也都避开了父亲的编号。
---
## 但你的贪心在顺序 A→B→C 时会失败
你的规则（对应代码）是：
- `t`：按 1,2,3… 递增发新编号
- 如果当前点禁用 `t`，就“跳过”它：把 `t` 存到洞 `g`，然后给它 `t+1`
- 若 `g` 存在且当前点不禁用 `g`，就先把洞 `g` 填给它
现在按顺序 **A, B, C** 跑：
### 处理 A（禁 1）
- `t=1`，但 A 禁 1 ⇒ 产生洞 `g=1`，`t` 再加到 2
- 给 A：`du[A]=2`
### 处理 B（禁 2）
- 此时 `g=1`，而 B 的父亲编号是 2，**不等于 1** ⇒ 贪心立刻把洞填掉
- 给 B：`du[B]=1`，洞清空
### 处理 C（禁 3）
- 现在已用掉 {2,1}，`t` 会走到 3
- 但 C 禁 3 ⇒ 贪心只能跳过 3，给它 4
- 得到 `du[C]=4 > ans(=3)` ⇒ **这层构造失败，重来**
所以你看到的现象就是：**同样的一层，同样的 K，有的顺序一把过，有的顺序必炸。**