Hello 2026——D2. Tree Coloring (Hard Version)（随机化算法可以分层实现）（猜测答案时，可以先猜测一个下界然后尝试不断提升）

题目大意

问题描述:

给定一棵有 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$ 的贪心进行一个瞎搞。

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代码

/**
 * 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

/**
 * 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……）

走了一些弯路，做这种图论的题目，还是需要更有整体意识

源代码

/**
 * 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

显然存在合法分配（且都在 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，有的顺序一把过，有的顺序必炸。