題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 CF2183D1 Tree Coloring (Easy Version)

rating: 1532

Problem Statement

題目簡述

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

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

求將整棵樹染黑所需的最少操作次數。

Constraints

約束條件

$2 \le n \le 2 \cdot 10^5$

思路：分析下界

問題轉化：染色問題

題目要求最小化操作次數，我們可以將每次操作視為分配一種顏色。題意等同於：將樹上所有節點染色，使得相同顏色的節點之間「深度皆不同」且「不存在父子關係」，求最小的顏色數量 $K$ 。

在轉化後的問題下，我們可以分析對顏色數量的下界限制：

1. 每層顏色互異

考慮樹的每一層（相同深度的節點集合）。
根據限制，相同顏色的節點深度必須不同，這意味著同一層的所有節點必須染上不同的顏色。
若第 $d$ 層有 $|L_d|$ 個節點，則顏色數量至少需要 $|L_d|$ 。

Ans \ge \max_d |L_d|

2. 父子及其兄弟互斥

考慮任意一個節點 $u$ 及其所有子節點 $v_1, v_2, \dots, v_k$ 。

子節點間互斥：所有子節點 $v_i$ 都在同一層（深度均為 $depth(u)+1$ ），根據深度限制，它們必須顏色互異。
父子互斥：父節點 $u$ 與每個子節點 $v_i$ 之間存在父子關係（邊），根據限制，它們不能同色。

綜合上述兩點，集合 $\{u, v_1, v_2, \dots, v_k\}$ 中的任意兩個節點，要麼深度相同，要麼是父子關係，因此這個集合內的所有節點都必須染上不同的顏色。
這個互斥集合的大小為 $k+1$ （1 個父節點 + $k$ 個子節點）。

Ans \ge \deg_{child}(u) + 1

結論

所需的最少顏色數量（操作次數）即為上述兩個下界的最大值。

Ans = \max \left( \max_{d} |L_d|, \quad \max_{u} (\deg_{child}(u) + 1) \right)

我們將在 Hard Version 中構造一組染色方案，證明此下界可達。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，需要計算出每個節點的深度和度數。
空間複雜度： $\mathcal{O}(n)$ 。

Code

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)

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

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