题目分析

题意理解

我们有一棵树，需要计算：

• 选择若干个城市形成连通块
• 在选择的城市中，第k危险的城市（按危险程度排名第k）的危险程度
• 对所有可能的连通块求和

关键难点

1. 连通性约束：选择的城市必须形成连通块
2. 第k大值：需要统计每个连通块中第k大的危险程度
3. 组合计数：需要高效计算所有可能的连通块

算法思路

核心思想：枚举阈值 + 树形DP

1. 阈值枚举

对于每个可能的危险程度值 d，考虑：

• 将所有城市分为两类：危险程度 ≥ d 和 < d
• 计算包含至少k个危险程度 ≥ d 的城市的连通块数量

2. 容斥计算

通过枚举阈值，使用容斥原理：

答案 = ∑_{d} (包含至少k个≥d城市的连通块数量) × (d的贡献)

3. 树形DP

定义 dp[u][j] 表示在以u为根的子树中，选择了j个危险程度 ≥ 当前阈值的节点的连通块方案数。

代码详解

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 2e3 + 10, mod = 64123;
int n, lim, V;
int dp[N][N];      // dp[u][j]: 在u的子树中选j个达标节点的方案数
int siz[N];        // 子树大小
int val[N];        // 当前节点是否达标(危险程度≥阈值)
int d[N];          // 原始危险程度
int ys[N];         // 离散化后的危险程度
int tot, ans;      // 总答案
int id[N], idx, rev[N];  // 树链剖分相关
vector<int> v[N];  // 邻接表
ll g[N], f[N];     // 临时数组

// 添加边
inline void addedge(int x, int y) {
    v[x].emplace_back(y);
    v[y].emplace_back(x);
}

// 树链剖分预处理
inline void init(int x, int y) {
    rev[id[x] = ++idx] = x;  // 记录DFS序
    
    for (int i : v[x])
        if (i != y)
            init(i, x);
}

// 树形DP主过程
void DP() {
    // 逆DFS序处理（从叶子到根）
    for (int i = n; i; --i) {
        int x = rev[i];
        
        // 初始化当前节点
        dp[x][siz[x] = val[x]] = 1;  // 选择当前节点
        
        // 合并子树
        for (int i : v[x]) {
            if (id[x] < id[i]) {  // 确保是子节点
                register int j = 0, k = 0;
                
                // 使用循环展开优化
                // 复制当前dp值到临时数组
                for (j = 0; j <= siz[x] + siz[i] - 3; j += 4) {
                    g[j] = f[j] = dp[x][j];
                    g[j + 1] = f[j + 1] = dp[x][j + 1];
                    g[j + 2] = f[j + 2] = dp[x][j + 2];
                    g[j + 3] = f[j + 3] = dp[x][j + 3];
                }
                while (j <= siz[x] + siz[i]) {
                    g[j] = f[j] = dp[x][j];
                    ++j;
                }
                
                // 合并子树方案数
                for (j = 0; j <= siz[x]; ++j) {
                    for (k = 0; k <= siz[i] - 3; k += 4) {
                        g[j + k] += (dp[i][k] * f[j]);
                        g[j + k + 1] += (dp[i][k + 1] * f[j]);
                        g[j + k + 2] += (dp[i][k + 2] * f[j]);
                        g[j + k + 3] += (dp[i][k + 3] * f[j]);
                    }
                    while (k <= siz[i]) {
                        g[j + k] += (dp[i][k] * f[j]);
                        ++k;
                    }
                }
                
                siz[x] += siz[i];  // 更新子树大小
                
                // 取模并写回dp数组
                for (j = 0; j <= siz[x] - 3; j += 4) {
                    dp[x][j] = g[j] % mod;
                    dp[x][j + 1] = g[j + 1] % mod;
                    dp[x][j + 2] = g[j + 2] % mod;
                    dp[x][j + 3] = g[j + 3] % mod;
                }
                while (j <= siz[x]) {
                    dp[x][j] = g[j] % mod;
                    ++j;
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> lim >> V;
    
    // 读入危险程度
    for (int i = 1; i <= n; ++i) {
        cin >> d[i];
        ys[i] = d[i];
    }
    
    // 离散化危险程度
    sort(ys + 1, ys + 1 + n);
    tot = unique(ys + 1, ys + 1 + n) - ys - 1;
    ys[tot + 1] = ys[tot] + 1;  // 哨兵
    
    // 读入树边
    for (int i = 1, x, y; i < n; ++i) {
        cin >> x >> y;
        addedge(x, y);
    }
    
    // 树链剖分预处理
    init(1, 0);
    
    // 枚举阈值
    for (int i = 1; i <= tot; ++i) {
        // 统计达标节点数量
        int ct = 0;
        for (int j = 1; j <= n; ++j)
            ct += (val[j] = (d[j] >= ys[i]));
        
        // 如果没有足够多的达标节点，直接退出
        if (ct < lim) break;
        
        // 运行树形DP
        DP();
        
        // 统计包含至少lim个达标节点的连通块数量
        ll res1 = 0, res2 = 0, res3 = 0, res4 = 0;
        register int j, k;
        
        for (j = 1; j <= n; ++j) {
            // 循环展开优化统计
            for (k = lim; k <= siz[j] - 3; k += 4) {
                res1 += dp[j][k];
                res2 += dp[j][k + 1];
                res3 += dp[j][k + 2];
                res4 += dp[j][k + 3];
            }
            while (k <= siz[j])
                res1 += dp[j][k++];
            
            // 清空dp数组
            for (k = 0; k <= siz[j] - 3; k += 4) {
                dp[j][k] = 0;
                dp[j][k + 1] = 0;
                dp[j][k + 2] = 0;
                dp[j][k + 3] = 0;
            }
            while (k <= siz[j])
                dp[j][k++] = 0;
        }
        
        // 计算贡献：数量 × (当前阈值 - 上一个阈值)
        ans += (res1 + res2 + res3 + res4) * (ys[i] - ys[i - 1]) % mod;
    }
    
    cout << ans % mod << '\n';
    return 0;
}

算法核心要点详解

1. 容斥原理的应用

对于第k大的值为d，等价于：

• 至少有k个节点的危险程度 ≥ d
• 但不能所有节点的危险程度都 ≥ d+1（否则第k大的值会更大）

因此贡献为：(≥d的方案数 - ≥d+1的方案数) × d

2. 树形DP状态设计

dp[u][j] 表示在以u为根的子树中：

• 选择包含u的连通块
• 其中有j个节点的危险程度 ≥ 当前阈值

转移时使用背包合并子树。

3. 优化技巧

• 循环展开：手动展开内层循环，减少循环开销
• 临时数组：使用g[]和f[]避免重复计算
• 树链剖分：确定处理顺序，确保子节点先于父节点处理
• 提前终止：当达标节点数不足k时直接退出

4. 离散化处理

将危险程度离散化，减少需要枚举的阈值数量。

复杂度分析

• 阈值枚举：O(tot) ≤ O(n)
• 树形DP：O(n × n) 每个阈值
• 总复杂度：O(n³) 但通过优化可以接受 n≤1666 的数据

总结

这道题综合运用了：

1. 容斥原理 处理第k大值的计数
2. 树形DP 计算连通块方案数
3. 离散化 优化枚举过程
4. 循环展开 等底层优化技巧

是一个很好的树形计数问题，考察了对组合数学和动态规划的综合运用能力。