题目分析

题意理解

我们有一棵树，每个节点有重量和价值。需要解决两个层次的问题：

1. 完美的集合：重量和 ≤ M 的连通节点集合，且价值之和最大
2. 测试可行性：选择 K 个完美集合，存在一个测试点 x 满足：
   • x 在所有选中的集合中
   • 对每个集合 S 和每个 y∈S，有 dist(x,y)×v_y ≤ Max

关键难点

1. 双重约束：既要重量限制，又要测试功率限制
2. 组合计数：需要计算满足条件的 K 元组数量
3. 大模数：模数 11920928955078125 = 5²³

算法思路

整体框架：容斥原理 + 树形DP

1. 寻找完美集合

• 枚举每个点作为根，做树形DP
• dp[i][j][0/1] 表示在子树 i 中，重量为 j 时的最大价值和方案数

2. 处理测试点约束

使用容斥原理：

• 对于边 (u,v)，计算以该边为"分界线"的情况
• 通过包含-排除原理计算恰好满足条件的方案

3. 组合数计算

由于模数特殊（只有质因子5），使用扩展卢卡斯定理计算组合数

代码详解

#include <bits/stdc++.h>
#define int long long
#define i128 __int128
using namespace std;

int n, m, k, maxdis;
int MOD = 1;  // 5^23
int dis[63][63], e[63][3], cst[63], val[63];
int cst2[63], val2[63], dp[63][10003][2];
int ans, num[63], maxv, c[25][25];
vector<int> E[63];

// 快速幂
int fstp(int xx, int yy) {
    i128 ret = 1, bse = xx % MOD;
    while (yy) {
        if (yy % 2) ret = ret * bse % MOD;
        bse = bse * bse % MOD;
        yy /= 2;
    }
    return ret;
}

// 树形DP计算完美集合
void dfs(int now, int fa) {
    for (auto i : E[now]) {
        if (i == fa) continue;
        
        // 初始化子节点DP数组
        for (int j = 0; j < cst2[i]; j++) {
            dp[i][j][0] = -100000000000ll;
            dp[i][j][1] = 0;
        }
        
        // 状态转移
        for (int j = 0; j + cst2[i] <= m; j++) {
            dp[i][j + cst2[i]][0] = dp[now][j][0] + val2[i];
            dp[i][j + cst2[i]][1] = dp[now][j][1];
        }
        
        dfs(i, now);
        
        // 合并子树结果
        for (int j = 0; j <= m; j++) {
            if (dp[i][j][0] > dp[now][j][0]) {
                dp[now][j][0] = dp[i][j][0];
                dp[now][j][1] = 0;
            }
            if (dp[i][j][0] == dp[now][j][0])
                dp[now][j][1] += dp[i][j][1];
        }
    }
    return;
}

// 计算n!中因子5的个数
int g(int xx) {
    if (xx < 5) return 0;
    return (xx / 5) + g(xx / 5);
}

// 多项式结构，用于计算特殊阶乘
struct Poly {
    int len;
    int v[25];  // 系数数组
} ret, bse, spv;

// 多项式乘法
void prod(Poly &xx, Poly yy) {
    spv.len = yy.len;
    
    // 计算多项式系数
    for (int i = 0; i < 23; i++) {
        spv.v[i] = 0;
        if (yy.v[i] == 0) continue;
        
        i128 uu = yy.v[i];
        for (int j = i; j >= 0; j--, uu = uu * (5ll * xx.len) % MOD)
            spv.v[j] = (spv.v[j] + uu * c[i][j]) % MOD;
    }
    
    // 合并多项式
    for (int i = 22; i >= 0; i--) {
        i128 u = xx.v[i];
        if (u == 0) continue;
        
        xx.v[i] = 0;
        for (int j = 0; j + i < 23; j++)
            xx.v[i + j] = (xx.v[i + j] + u * spv.v[j]) % MOD;
    }
    
    xx.len += yy.len;
    return;
}

// 计算特殊多项式值
int calc(int xx) {
    if (xx == 0) return 1;
    
    memset(bse.v, 0, sizeof(bse.v));
    memset(ret.v, 0, sizeof(ret.v));
    ret.v[0] = 1;
    
    // 设置基多项式：(5x+1)(5x+2)...(5x+5) 的系数
    bse.v[0] = 24;  // 1*2*3*4
    bse.v[1] = 50;  // 系数计算得到
    bse.v[2] = 35;
    bse.v[3] = 10;
    bse.v[4] = 1;
    bse.len = 1;
    
    // 快速幂计算多项式
    while (xx) {
        if (xx % 2) prod(ret, bse);
        prod(bse, bse);
        xx /= 2;
    }
    
    return ((ret.v[0] % MOD) + MOD) % MOD;
}

// 计算去掉因子5后的阶乘
int f(int xx) {
    if (xx <= 1) return 1;
    if (xx % 5 != 0) {
        i128 ret = f(xx - 1);
        ret = ret * xx % MOD;
        return ret;
    }
    
    i128 ret = f(xx / 5);
    ret = ret * calc(xx / 5) % MOD;
    return ret;
}

int vvv = 0;
map<int, int> mp;

// 计算组合数 C(xx, yy) mod 5^23
int C(int xx, int yy) {
    if (mp.find(xx) != mp.end()) return mp[xx];
    
    // 使用扩展卢卡斯定理
    i128 ret = fstp(5, g(xx) - g(yy) - g(xx - yy));
    ret = ret * f(xx) % MOD;
    ret = ret * vvv % MOD;
    ret = ret * fstp(f(xx - yy), (MOD * 4ll / 5ll) - 1) % MOD;
    
    mp[xx] = ret;
    return ret;
}

// 计算以rt为根，系数为xs的贡献
void calc(int rt, int xs) {
    if (num[rt] == 0) return;
    
    // 重建树结构（只包含有效节点）
    for (int i = 1; i <= n; i++) {
        E[i].clear();
        E[i].shrink_to_fit();
    }
    
    for (int i = 1; i < n; i++) {
        if (num[e[i][0]] == num[e[i][1]] || num[e[i][0]] == 0 || num[e[i][1]] == 0)
            continue;
        E[num[e[i][0]]].emplace_back(num[e[i][1]]);
        E[num[e[i][1]]].emplace_back(num[e[i][0]]);
    }
    
    memset(cst2, 0, sizeof(cst2));
    memset(val2, 0, sizeof(val2));
    
    // 初始化DP数组
    for (int j = 0; j <= m; j++) {
        dp[rt][j][0] = -100000000000ll;
        dp[rt][j][1] = 0;
    }
    
    // 重新映射节点权重和价值
    for (int i = 1; i <= n; i++) {
        cst2[num[i]] += cst[i];
        val2[num[i]] += val[i];
    }
    
    // 设置根节点初始状态
    if (cst2[rt] <= m) {
        dp[rt][cst2[rt]][0] = val2[rt];
        dp[rt][cst2[rt]][1] = 1;
    } else return;
    
    // 树形DP
    dfs(rt, 0);
    
    // 统计完美集合数量
    int u = 0;
    for (int i = 0; i <= m; i++)
        if (dp[rt][i][0] == maxv)
            u += dp[rt][i][1];
    
    if (u < k || xs == 0) return;
    
    // 计算组合贡献
    ans = (ans + xs * C(u, k)) % MOD;
    return;
}

signed main() {
    ios::sync_with_stdio(false);
    
    // 预处理组合数
    for (int i = 0; i <= 24; i++) c[i][0] = 1;
    for (int i = 1; i <= 24; i++) {
        for (int j = 1; j <= i; j++)
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
    }
    
    // 设置模数 5^23
    for (int i = 1; i <= 23; i++) MOD = MOD * 5ll;
    
    cin >> n >> m >> k >> maxdis;
    
    // 读入数据
    for (int i = 1; i <= n; i++) cin >> cst[i];
    for (int i = 1; i <= n; i++) cin >> val[i];
    for (int i = 1; i < n; i++) 
        cin >> e[i][0] >> e[i][1] >> e[i][2];
    
    // Floyd计算所有点对最短距离
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            dis[i][j] = 100000000000ll;
    }
    
    for (int i = 1; i < n; i++)
        dis[e[i][0]][e[i][1]] = dis[e[i][1]][e[i][0]] = e[i][2];
    
    for (int i = 1; i <= n; i++) dis[i][i] = 0;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int u = 1; u <= n; u++)
                dis[j][u] = min(dis[j][u], dis[j][i] + dis[i][u]);
        }
    }
    
    vvv = fstp(f(k), (MOD * 4ll / 5ll) - 1);
    
    // 步骤1: 计算最大价值maxv
    for (int uu = 1; uu <= n; uu++) {
        for (int i = 1; i <= n; i++) num[i] = i;
        calc(uu, 0);
        for (int j = 0; j <= m; j++)
            maxv = max(maxv, dp[uu][j][0]);
    }
    
    // 步骤2: 计算节点作为测试点的贡献
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) num[j] = j;
        
        // 标记不满足距离约束的节点
        for (int j = 1; j <= n; j++)
            if (dis[i][j] * val[j] > maxdis)
                num[j] = 0;
        
        calc(i, 1);  // 系数为1
    }
    
    // 步骤3: 计算边作为"分界"的容斥贡献
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= n; j++) num[j] = j;
        
        // 合并边的两个端点
        num[e[i][0]] = e[i][1];
        
        // 标记不满足距离约束的节点
        for (int j = 1; j <= n; j++)
            if (dis[e[i][0]][j] * val[j] > maxdis || dis[e[i][1]][j] * val[j] > maxdis)
                num[j] = 0;
        
        if (num[e[i][0]] == 0 || num[e[i][1]] == 0) continue;
        
        calc(e[i][1], -1);  // 系数为-1，用于容斥
    }
    
    ans %= MOD;
    ans += MOD;
    ans %= MOD;
    cout << ans << '\n';
    return 0;
}

算法核心要点详解

1. 容斥原理的应用

对于测试点约束，我们计算：

• 包含计算：对每个点作为测试点计算贡献
• 排除重复：对每条边，减去被重复计算的情况
• 最终结果 = ∑点贡献 - ∑边贡献

2. 树形DP设计

dp[i][j][0/1] 状态定义：

• dp[i][j][0]：以i为根的子树，重量为j时的最大价值
• dp[i][j][1]：达到最大价值的方案数

转移时注意连通性的维护。

3. 扩展卢卡斯定理

由于模数只有质因子5，使用特殊方法计算组合数：

• 分离5的因子：g(n) 计算n!中5的个数
• 计算去掉5后的阶乘：f(n)
• 使用多项式方法快速计算

4. 节点重标号技巧

通过num[]数组：

• num[i] = 0 表示节点i被排除
• num[i] = num[j] 表示节点i和j被合并 这样可以在容斥时统一处理

复杂度分析

• Floyd：O(n³) = 60³ = 216,000
• 树形DP：O(n × m × n) = 60 × 10000 × 60 = 36,000,000
• 组合数计算：使用记忆化，总体可接受

总结

这道题综合运用了：

1. 树形DP 处理连通集合
2. 容斥原理 处理测试点约束
3. 扩展卢卡斯定理 计算大组合数
4. 最短路算法 预处理距离
5. 多项式技巧 高效计算特殊阶乘

是一个很好的综合题目，考察了树形DP、容斥原理、组合数学等多个重要算法思想。