Codeforces 486D Valid Sets：樹形 DP + 以最小值為根的計數技巧

題目大意

給定 n 個節點的樹，每個節點有權值 a[i]。求滿足條件的非空點集數量：
1. 點集內任意兩點連通（即為一棵連通子樹）
2. max(權值) - min(權值) ≤ d
答案模 1e9+7。

核心思路：枚舉最小值節點為根

對每個節點 u，計算「包含 u 且 u 為點集中權值最小（權值相同則編號最小）的合法連通子樹數量」。
最終答案 = 所有節點作為最小值根的合法子樹數量之和。

避免重複計數的關鍵約束

在以 u 為根的 DFS 中，只能走向滿足以下條件的鄰居 v：

• a[v] > a[u]，或
• a[v] == a[u] 且 v > u（編號大於 u，保證同權值時只以編號最小的為根）
• a[v] - a[u] ≤ d（權值差不超過 d）

狀態轉移方程

dfs(u, fa, root) 返回以 u 為根的子樹中，包含 u 且滿足上述約束的合法連通子樹數量。
ans = 1（只包含 u 自身）
對每個合法子節點 v：
ans = ans * (dfs(v, u, root) + 1) % MOD
+1 表示不選 v 這棵子樹的方案。

Java 參考實現（簡化版）

int dfs(int u, int fa, int root) {
    long res = 1;
    for (int v : adj[u]) {
        if (v == fa) continue;
        if (a[v] < a[root] || (a[v] == a[root] && v < root)) continue;
        if (a[v] - a[root] > d) continue;
        res = res * (dfs(v, u, root) + 1) % MOD;
    }
    return (int)res;
}

void solve() {
    for (int i = 1; i <= n; ++i)
        ans = (ans + dfs(i, 0, i)) % MOD;
}

複雜度分析

• 每個節點作為根做一次 DFS，但實際訪問的邊總數為 O(n^2) 最壞情況。
• 數據範圍 n ≤ 2000，O(n^2) 可接受。
• 優化：按權值排序 + 並查集 / 雙指針可降至 O(n log n)，但代碼複雜度大增，比賽中 O(n^2) 往往足夠。

避坑指南

1. 同權值去重：必須加上 v > root 條件，否則同權值連通塊會被多根計數。
2. 模運算：乘法前轉 long 防溢出，每步取模。
3. 遞歸深度：n=2000 遞歸通常安全，極端鏈狀樹可改迭代或增棧。