🔗 CF2183D2 Tree Coloring (Hard Version)

rating: 2066

Problem Statement

題目簡述

這是題目的 Hard Version。與 Easy Version 的區別在於：本題不僅要求求出最小的操作次數，還需要構造出具體的染色方案。

給定一棵 nn 個節點、以 11 為根的有根樹。每次操作可以選擇一個白色節點集合 SS，將其染黑。集合 SS 需滿足：

  1. 集合內任意兩點之間沒有邊相連（即 SS 為獨立集）。
  2. 集合內任意兩點到根節點的距離不同。

找出將整棵樹染黑所需的最少操作次數，並輸出每次操作所選擇的節點集合。

Constraints

約束條件

  • 2≤n≤2⋅1052 \le n \le 2 \cdot 10^5

思路：貪心構造

根據 Easy Version 的分析，最小操作次數 AnsAns 受限於兩個下界：

  • max⁡∣Ld∣\max |L_d|：同一層的節點必須不同色。
  • deg⁡child(u)+1\deg_{child}(u) + 1：一個父節點 uu 與其所有子節點互異，形成大小為 deg⁡child(u)+1\deg_{child}(u) + 1 的集合，兩兩必須不同色。
結論

所需的最少顏色數量 kk 為兩個下界的最大值。

k=max⁡(max⁡d∣Ld∣,max⁡u(deg⁡child(u)+1))k = \max \left( \max_{d} |L_d|, \quad \max_{u} (\deg_{child}(u) + 1) \right)

kk 即為所需的最小顏色數。

此外，由於節點 uu 的所有子節點必在同一層，故 deg⁡child(u)≤max⁡d∣Ld∣\deg_{child}(u) \leq \max_d |L_d|，進而 max⁡u(deg⁡child(u)+1)≤max⁡d∣Ld∣+1\max_u (\deg_{child}(u) + 1) \leq \max_d |L_d| + 1，即 k≤max⁡d∣Ld∣+1k \leq \max_d |L_d| + 1。

構造策略

我們採用由上到下 逐層貪心 的策略來構造，按深度 d=1,2,…d = 1, 2, \dots 順序，逐層為節點染色。

  • 對於第 dd 層，節點集合為 LdL_d，大小 m=∣Ld∣m = |L_d|。
  • 我們先分配 0…m−10 \dots m-1 給這些節點。

此時分配後可以滿足層內互異，以及子節點間互異，僅剩下父節點與子節點同色的衝突。

衝突解決方案

如何解決「節點 uu 與其父節點 fa[u]fa[u] 同色」的衝突？

檢查所有 u∈Ldu \in L_d，找出衝突集合 Bad={u∣color[u]==color[fa[u]]}Bad = \{ u \mid color[u] == color[fa[u]] \}。根據 p:=∣Bad∣p := |Bad| 的大小分類討論：

Case 1: 多個衝突點 (p≥2p \ge 2)

構造策略：循環位移 (Rotation)

設這些衝突點當前分配的顏色（與其父節點顏色相同）為 c1,c2,…,cpc_1, c_2, \dots, c_{p}。
由於父節點都在上一層，且上一層顏色互異，故 c1…cpc_1 \dots c_{p} 各不相同。
我們將這些衝突點的顏色進行 循環位移：

  • u1u_1 改染 c2c_2
  • u2u_2 改染 c3c_3
  • …\dots
  • upu_{p} 改染 c1c_1

移位後，與父節點的衝突可以解決，且層內元素依然使用這組顏色集合，僅分配對象改變，不破壞層內互異性。

Case 2: 只有一個衝突點 (p=1p = 1)

構造策略：換色或交換 (Swap)

設衝突點為 uu，顏色為 cc（父節點也是 cc），考慮兩種情況：

  1. 若顏色未用滿 (m<km < k)：
    直接將 uu 改染一個未使用的顏色，如 mm。

  2. 若顏色已用滿 (m=km = k)：
    必須在同層中找另一個節點 vv，滿足 color[fa[v]]≠ccolor[fa[v]] \neq c，將 uu 和 vv 的顏色交換。

存在性證明：為何一定能找到可交換的 vv？

假設無法找到這樣的 vv，即同層所有節點的父節點顏色都是 cc。又因為顏色已經用滿，此時父節點顏色為 cc 的節點數量為 kk 個。

這些父節點都在上一層 Ld−1L_{d-1}，分兩種情況討論：

  • 若這些父節點互不相同：則上一層有 kk 個節點顏色都是 cc，違反「同層不同色」。
  • 若這些父節點是同一個節點 fafa：則 fafa 有 kk 個子節點。加上 fafa 自己，這個集合大小為 k+1k + 1，但我們計算 kk 時已取了 max⁡(deg⁡child(fa)+1)\max(\deg_{child}(fa) + 1)，產生矛盾。

綜上，必然存在一個 vv，其父節點顏色不是 cc，可以與 uu 安全交換。

複雜度分析

  • 時間複雜度：O(n)\mathcal{O}(n)。
  • 空間複雜度：O(n)\mathcal{O}(n)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
from collections import deque, defaultdict

def solve():
    n = int(input())
    g = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(lambda x: int(x) - 1, input().split())
        g[u].append(v)
        g[v].append(u)

    ans = 0
    q = deque([0])
    dist = [0] * n
    fa = [0] * n
    fa[0] = -1
    while q:
        u = q.popleft()
        for v in g[u]:
            if v == fa[u]:
                continue
            dist[v] = dist[u] + 1
            fa[v] = u
            q.append(v)
        ans = max(ans, sum(1 for v in g[u] if v != fa[u]) + 1)

    layers = defaultdict(list)
    for u in range(n):
        layers[dist[u]].append(u)

    k = max(ans, max(len(layers[d]) for d in layers))

    color = [0] * n
    color[0] = 0
    for d in range(1, max(layers.keys()) + 1):
        arr = layers[d]
        for i, u in enumerate(arr):
            color[u] = i

        nodes = [i for i, u in enumerate(arr) if fa[u] != -1 and color[fa[u]] == color[u]]
        if len(nodes) == 1:
            idx = nodes[0]
            u = arr[idx]
            c = color[u]
            if (m := len(arr)) < k:
                color[u] = m
            else:
                for j, v in enumerate(arr):
                    if color[fa[v]] != c:
                        color[arr[idx]], color[arr[j]] = color[arr[j]], color[arr[idx]]
                        break
                else:
                    assert False, "No valid v found"
        elif len(nodes) >= 2:
            c = color[arr[nodes[0]]]
            for j in range(len(nodes) - 1):
                color[arr[nodes[j]]] = color[arr[nodes[j + 1]]]
            color[arr[nodes[-1]]] = c

    ops = [[] for _ in range(k)]
    for u in range(n):
        ops[color[u]].append(u + 1)

    print(len(ops))
    for op in ops:
        print(len(op), *op)

    tot = sum(len(op) for op in ops)
    assert tot == n, f"tot = {tot}, n = {n}"

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

寫在最後

PROMPT

masterpiece, best quality, high quality, good quality, 32K UHD, colorful, official art, illustration, in the style of fashion photography, dynamic, dynamic force picture, (Visual impact:1.2), impactful picture, extreme aesthetic, A shot with tension, sharp focus, The Ninth Art, depth of field, cinematic lighting, light particles, lens flare, movie perspective, (Tyndall Effect:1.4), light particles, light, shadow, scenery, temperate atmosphere, (artist:pigeon666:0.83), (Yomu:0.4), (remsrar:0.45), (quasarcake:0.3),

1girl, solo, Nijika Ijichi (ijichi nijika, bocchi the rock), brown eyes, blonde hair, long hair, very long hair, bangs, side ponytail, school uniform, white shirt, pleated skirt, long sleeves, bow, ahoge, sidelocks, outdoors, collared shirt, bowtie, black skirt, bag, red bow, red bowtie,

holding umbrella, transparent umbrella, rain, raining, night, wet street, puddle, reflection, glowing vending machine, backlighting, neon lights, urban scenery, wide shot, landscape, horizontal, looking at viewer, blush