[集训队互测 2018] 完美的集合

GitHub跳转原题关系图返回列表

按最大点权和筛出连通块，用「最浅合法测试点」把存在公共测试点拆成单点计数，DFS 序背包 O(N²M) 求各 A_x，再算 C(A_x,K) mod 5^23（注意 A_x 要精确到 u64、方案数不能取模）。

OJ: luogu

题目 ID: P9248

难度:省选/NOI-

标签:树形 DP背包组合数数论DFS 序

创建: 2026-10-02 15:07

更新: 2026-10-03 18:30

目录

  1. 形式化题目
  2. 暴力解法
    1. 思路
    2. 代码
    3. 复杂度
    4. 瓶颈
  3. 正解
    1. 思路
      1. 代码
      2. 复杂度
    2. 总结

    形式化题目

    给定一棵 NN 个点的带权树，点 ii 有重量 wiw_i 与价值 viv_i（viv_i 可为 00），边有长度。记点集 SS 的重量 W(S)=∑i∈SwiW(S)=\sum_{i\in S} w_i、价值 V(S)=∑i∈SviV(S)=\sum_{i\in S} v_i。

    称非空连通点集 SS 为完美的集合，若它的价值是「重量不超过 MM 的连通点集」中最大的，即

    V\*=max⁡{V(S):W(S)≤M, S 非空连通},S∈P  ⟺  V(S)=V\*. V^\*=\max\{V(S): W(S)\le M,\ S\text{ 非空连通}\},\qquad S\in\mathcal P\iff V(S)=V^\* .

    对一个点 xx，称 xx 适用于 SS（是 SS 的合法测试点），若

    x∈S且∀y∈S: dist⁡(x,y) vy≤Max. x\in S\quad\text{且}\quad \forall y\in S:\ \operatorname{dist}(x,y)\,v_y\le Max .

    求从 P\mathcal P 中选出 KK 个互不相同的集合（无序）的方案数，使得存在一个点 xx 同时适用于这 KK 个集合，即它们合法测试点集合的交非空。答案对 11920928955078125=52311920928955078125=5^{23} 取模。

    N≤60N\le 60，M≤104M\le 10^4，K≤109K\le 10^9，Max≤1018Max\le 10^{18}。

    样例推演。 样例的完美集合只有 {1,2,5},{1,4},{2,6}\{1,2,5\},\{1,4\},\{2,6\}（价值均为 33）。同时适用于前两个的点 x=1x=1，适用于第一、三个的点 x=2x=2，而第二、三个没有公共测试点，故选 K=2K=2 个的方案数为 22。

    暴力解法

    思路

    NN 只有几十，最直接的想法是把所有点集都枚举出来：

    1. 枚举所有非空子集（2N2^N 个），先按重量 W(S)≤MW(S)\le M 筛掉一部分，再用一次 BFS/DFS 检查它在树上是否连通；
    2. 在所有「连通且重量达标」的集合里求出最大价值 V\*V^\*，把价值等于 V\*V^\* 的集合收进 P\mathcal P；
    3. 对每个完美集合 SS，枚举 x∈Sx\in S 检查它是否合法（对 SS 内每个 yy 验证 dist⁡(x,y)vy≤Max\operatorname{dist}(x,y)v_y\le Max），得到 SS 的合法测试点集合；
    4. 暴力枚举 P\mathcal P 的所有 KK 元组合，检查这 KK 个集合的合法测试点集合是否有交。

    代码

    cpp
    /**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:07
 * update_at: 2026-10-03 18:25
 */
// P9248 暴力对拍解：直接按题意枚举。
//
// 1. 枚举所有非空点集（生成器保证 N <= 15），筛出连通且重量和 <= M 的。
// 2. 求最大点权和 V*，把点权和等于 V* 的集合记为完美集合。
// 3. 对每个完美集合 S 求出它的合法测试点集合（x ∈ S 且对 S 内每点 y
//    有 dist(x,y)*v_y <= Max）。
// 4. 暴力枚举完美集合中所有 C(|P|, K) 种 K 元选择，检查是否存在一个点
//    同时出现在这 K 个集合的合法测试点集合里。
//
// 只适用于 K 很小、|P| 很小的对拍数据（生成器保证 K <= 4、|P| <= 60）。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long u64;

static const u64 MOD = 11920928955078125ULL;

static int N, M;
static ll K, Max;
static ll w[64], v[64];
static ll dist_[64][64];
static vector<pair<int,ll>> g[64];

int main() {
    scanf("%d %d %lld %lld", &N, &M, &K, &Max);
    for (int i = 0; i < N; i++) scanf("%lld", &w[i]);
    for (int i = 0; i < N; i++) scanf("%lld", &v[i]);
    for (int i = 0; i < N - 1; i++) {
        int a, b; ll c;
        scanf("%d %d %lld", &a, &b, &c);
        a--; b--;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    const ll INF = (ll)4e18;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) dist_[i][j] = (i == j ? 0 : INF);
        // BFS 求单源最短路（边权非负）
        priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
        dist_[i][i] = 0; pq.push({0, i});
        while (!pq.empty()) {
            auto pr = pq.top(); pq.pop();
            int u = pr.second; ll d = pr.first;
            if (d > dist_[i][u]) continue;
            for (auto &e : g[u]) {
                int to = e.first; ll nd = d + e.second;
                if (nd < dist_[i][to]) { dist_[i][to] = nd; pq.push({nd, to}); }
            }
        }
    }

    // 枚举所有非空子集
    vector<int> perf;          // 完美集合的 bitmask
    ll Vstar = -1;
    int total = 1 << N;
    for (int mask = 1; mask < total; mask++) {
        ll sw = 0, sv = 0;
        for (int i = 0; i < N; i++) if (mask >> i & 1) { sw += w[i]; sv += v[i]; }
        if (sw > M) continue;
        // 连通性：BFS
        int start = -1;
        for (int i = 0; i < N; i++) if (mask >> i & 1) { start = i; break; }
        int seen = 0;
        vector<int> stk = { start };
        vector<bool> vis(N, false);
        vis[start] = true;
        while (!stk.empty()) {
            int u = stk.back(); stk.pop_back(); seen++;
            for (auto &e : g[u]) {
                int to = e.first;
                if ((mask >> to & 1) && !vis[to]) { vis[to] = true; stk.push_back(to); }
            }
        }
        if (seen != __builtin_popcount((unsigned)mask)) continue;
        if (sv > Vstar) { Vstar = sv; perf.clear(); perf.push_back(mask); }
        else if (sv == Vstar) perf.push_back(mask);
    }

    if (Vstar < 0 || (ll)perf.size() < K || K < 1) { puts("0"); return 0; }

    // 每个完美集合的合法测试点
    int P = perf.size();
    vector<int> app(P, 0);
    for (int t = 0; t < P; t++) {
        int m = perf[t];
        for (int x = 0; x < N; x++) {
            if (!(m >> x & 1)) continue;
            bool ok = true;
            for (int y = 0; y < N; y++) {
                if (!(m >> y & 1)) continue;
                if (dist_[x][y] * v[y] > Max) { ok = false; break; }
            }
            if (ok) app[t] |= (1 << x);
        }
    }

    // 暴力枚举 K 元组合，检查是否存在公共测试点
    u64 ans = 0;
    vector<int> idx;
    function<void(int,int)> dfs = [&](int pos, int last) {
        if ((int)idx.size() == K) {
            int inter = app[idx[0]];
            for (int j = 1; j < K; j++) inter &= app[idx[j]];
            if (inter) ans = (ans + 1) % MOD;
            return;
        }
        for (int j = last + 1; j < P; j++) {
            idx.push_back(j);
            dfs(pos + 1, j);
            idx.pop_back();
        }
    };
    dfs(0, -1);
    printf("%llu\n", ans % MOD);
    return 0;
}

    复杂度

    枚举子集 O(2N⋅N2)O(2^N\cdot N^2)，求合法点 O(∣P∣⋅N2)O(|\mathcal P|\cdot N^2)，枚举 KK 元组合 O((∣P∣K)⋅NK)O(\binom{|\mathcal P|}{K}\cdot NK)。对 N≤15N\le 15、K≤4K\le 4、∣P∣|\mathcal P| 较小的数据完全可行，但对 N=60N=60、K=109K=10^9 完全不可行——光枚举子集就是 2602^{60}。

    瓶颈

    瓶颈有两个。第一是「枚举子集求完美集合」本身，第二——也是更要紧的——是最后一步的组合。KK 可以到 10910^9，就算 P\mathcal P 只有几千个集合，枚举 KK 元组合也天文数字。这说明最后的方案数一定可以用组合数整体表示，而不需要真的把组合选出来。这是正解的突破口。

    正解

    思路

    一、把「存在公共测试点」拆成单点计数

    记点 xx 的可行域

    Bx={y:dist⁡(x,y) vy≤Max}, B_x=\{y:\operatorname{dist}(x,y)\,v_y\le Max\},

    它总含 xx（dist⁡(x,x)=0\operatorname{dist}(x,x)=0）。于是 xx 适用于 SS 当且仅当 x∈S⊆Bxx\in S\subseteq B_x。

    关键观察：一个集合的合法测试点全体 W(S)W(S) 恒连通。 若 x,z∈W(S)x,z\in W(S)，取 xx 到 zz 的树上路径上任一点 uu。树度量满足 dist⁡(u,y)≤max⁡{dist⁡(x,y),dist⁡(z,y)}\operatorname{dist}(u,y)\le\max\{\operatorname{dist}(x,y),\operatorname{dist}(z,y)\}（投影性质），所以

    dist⁡(u,y) vy≤max⁡{dist⁡(x,y)vy, dist⁡(z,y)vy}≤Max, \operatorname{dist}(u,y)\,v_y\le \max\{\operatorname{dist}(x,y)v_y,\ \operatorname{dist}(z,y)v_y\}\le Max,

    即 uu 也合法，且 u∈Su\in S（SS 连通）。故 W(S)W(S) 是 SS 里的连通块。

    把树以 00 为根。一棵连通子树有唯一最浅点。对一组选出的 KK 个集合 TT，设

    X=⋂S∈TW(S)≠∅, X=\bigcap_{S\in T} W(S)\neq\varnothing,

    XX 是若干连通子树的交，仍是连通子树，故有唯一最浅点 x\*x^\*。按 x\*x^\* 分类计数，每组 TT 恰好被统计一次：

    #{T}=∑x[#{T: x∈X}−#{T: x∈X, fa⁡(x)∈X}]. \#\{T\}=\sum_{x}\big[\#\{T:\ x\in X\}-\#\{T:\ x\in X,\ \operatorname{fa}(x)\in X\}\big].

    记

    Ax=#{S∈P: x∈S⊆Bx},Cx=#{S∈P: {x,fa⁡(x)}⊆S⊆Bx∩Bfa⁡(x)}, A_x=\#\{S\in\mathcal P:\ x\in S\subseteq B_x\},\qquad C_x=\#\{S\in\mathcal P:\ \{x,\operatorname{fa}(x)\}\subseteq S\subseteq B_x\cap B_{\operatorname{fa}(x)}\},

    则「x∈Xx\in X」要求 KK 个集合都从「以 xx 为合法测试点」的 AxA_x 个里选，方案数 (AxK)\binom{A_x}{K}；「xx 与父亲都在 XX」要求从 CxC_x 个里选，方案数 (CxK)\binom{C_x}{K}（根没有父亲，该项为 00）。于是

     answer=∑x=1N[(AxK)−(CxK)]  \boxed{\ \text{answer}=\sum_{x=1}^{N}\Big[\binom{A_x}{K}-\binom{C_x}{K}\Big]\ }

    注意组合数是不放回的 (nK)\binom{n}{K}（选出 KK 个互不相同的集合）：样例里 33 个完美集合选 22 个、若允许重复会出现更多方案，与样例答案 22 矛盾。当 Ax<KA_x<K 时 (AxK)=0\binom{A_x}{K}=0。

    样例验证。 以 11 为根：A1=A2=2A_1=A_2=2、A4=A5=A6=1A_4=A_5=A_6=1、A3=A7=0A_3=A_7=0；父子交集 C2=C4=C5=C6=1C_2=C_4=C_5=C_6=1（都是 {1,2,5}\{1,2,5\} 那一类），C3=C7=0C_3=C_7=0，C1=0C_1=0（根）。代入：

    (22)+((22)−(12))+((11)−(11))+((11)−(11))+((11)−(01))=1+1=2. ✓ \binom22+\big(\binom22-\binom12\big)+\big(\binom11-\binom11\big)+\big(\binom11-\binom11\big)+\big(\binom11-\binom01\big)=1+1=2.\ \checkmark

    二、DFS 序背包求 AxA_x 与 CxC_x

    先求 V\*V^\*：对每个点 rr 强制选中 rr，做一次背包取最大价值，V\*V^\* 是对所有 rr 取最大。

    再对每个 xx 求 AxA_x。把树按 DFS 序拍成序列 p0,p1,…,pN−1p_0,p_1,\dots,p_{N-1}（以 xx 为根），维护 fi[ ]f_i[\,] 表示处理到第 ii 个位置的状态，容量记重量恰好为 cc（这是关键，见下）：

    • 选 pip_i：转移到 i+1i+1，重量加 wpiw_{p_i}，价值加 vpiv_{p_i}；
    • 不选 pip_i：它的整棵子树都不能再选（否则与已选部分不连通），直接跳到 i+size⁡(pi)i+\operatorname{size}(p_i)。

    每个状态记录「重量 →\to（最大价值，达到最大价值的方案数）」。单次 O(NM)O(NM)。

    **容量必须记「恰好为 cc」而不是「不超过 c」。** 如果记「不超过 $c」，两个价值相同、重量不同的集合会在同一个状态上被合并、方案数相加，导致计数错误（本题一个隐蔽的坑）。记「恰好为 $c」则每个集合对应唯一的决策序列，互不干扰。

    方案数不能取模！ 求出的 AxA_x 是后面组合数 (AxK)\binom{A_x}{K} 的精确输入——它依赖 AxA_x 的 55 进制展开，而不是 Ax mod 523A_x\bmod 5^{23}。好在 N≤60N\le 60 的树的连通点集个数最多是星形的 2N−1+N−1=259+592^{N-1}+N-1=2^{59}+59，恰好放得下 unsigned long long，所以背包里的方案数用 u64 精确保存、全程不取模，最后组合时再取模。

    求 CxC_x：把强制集合改成 {x,fa⁡(x)}\{x,\operatorname{fa}(x)\}、可行域改成 Bx∩Bfa⁡(x)B_x\cap B_{\operatorname{fa}(x)}。为了让两个强制点落在 DFS 序的前缀上，把 fa⁡(x)\operatorname{fa}(x) 安排成 xx 的第一个孩子（在 xx 为根的树里，父亲恰是它的一个孩子），同一套背包即可。总复杂度 O(N)O(N) 次 O(NM)O(NM)，即 O(N2M)=602×104≈3.6×107O(N^2M)=60^2\times10^4\approx3.6\times10^7。

    三、组合数 (nK) mod 523\binom{n}{K}\bmod 5^{23}

    nn 可达 2592^{59}、K≤109K\le 10^9，模数是素数幂 5235^{23}。扩展 Lucas 需要预处理长度 5235^{23} 的阶乘，不可能；用 Granville 素数幂组合数的变形：

    把 n!n! 里所有因子 55 剥出来，记

    U(m)=∏i=1m(i 去掉所有因子 5 后的部分)(mod523),v5(m!)=∑j≥1⌊m5j⌋, U(m)=\prod_{i=1}^{m}\big(i\text{ 去掉所有因子 }5\text{ 后的部分}\big)\pmod{5^{23}},\qquad v_5(m!)=\sum_{j\ge1}\Big\lfloor\frac{m}{5^j}\Big\rfloor,

    则

    (nK)=5 v5(n!)−v5(K!)−v5((n−K)!)⋅U(n)⋅U(K)−1⋅U(n−K)−1(mod523), \binom{n}{K}=5^{\,v_5(n!)-v_5(K!)-v_5((n-K)!)}\cdot U(n)\cdot U(K)^{-1}\cdot U(n-K)^{-1}\pmod{5^{23}},

    指数 ≥23\ge 23 时答案为 00。U(m)U(m) 与 55 互素故可逆。

    U(m)U(m) 有递归 U(m)=U(⌊m/5⌋)⋅G(m)U(m)=U(\lfloor m/5\rfloor)\cdot G(m)，其中

    G(m)=∏i≤m5∤ii=[∏r=14∏j<⌊m/5⌋(5j+r)]⋅∏r=1m mod 5(5⌊m/5⌋+r). G(m)=\prod_{\substack{i\le m\\ 5\nmid i}} i =\Big[\prod_{r=1}^{4}\prod_{j<\lfloor m/5\rfloor}(5j+r)\Big]\cdot\prod_{r=1}^{m\bmod 5}\big(5\lfloor m/5\rfloor+r\big).

    而 ∏j<t(5j+r)\prod_{j<t}(5j+r) 展开成以 55 为变量的幂级数，系数是初等对称多项式 ek(0,1,…,t−1)e_k(0,1,\dots,t-1)，它正是第一类 Stirling 数 ∣tt−k∣\bigl|{t\atop t-k}\bigr|；这是关于 tt 的 2k2k 次多项式，用牛顿级数 ∑ick,i(ti)\sum_i c_{k,i}\binom{t}{i} 求值（ck,ic_{k,i} 是整数差分系数），其中 (ti)\binom{t}{i}（i≤46i\le 46）把阶乘里的因子 55 剥掉再求逆元即可。单层 O(log⁡5n)O(\log_5 n)，预处理 O(462)O(46^2)，单次求组合数 O(log⁡5n⋅23⋅46)O(\log_5 n\cdot 23\cdot 46)。

    取模不是素数，所以 U(m)U(m) 里不能直接对普通阶乘求逆；上面全程只对「剥掉 55 因子后的部分」求逆，规避了这个问题。

    代码

    cpp
    /**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:07
 * update_at: 2026-10-03 18:25
 */
// P9248 [集训队互测 2018] 完美的集合
//
// 从所有「重量和 <= M 的连通块中点权和最大」的集合（完美集合）里选出 K 个
// （互不相同，无序），使得存在一个点 x 同时是这 K 个集合的合法测试点
// （x 在每个集合里，且对集合内每点 y 有 dist(x,y)*v_y <= Max）。
//
// 【第一步：整体条件拆成单点计数】
//   B_x = { y : dist(x,y)*v_y <= Max }（一定含 x），
//   A_x = #完美集合 S 满足 x ∈ S ⊆ B_x（即 x 是 S 的合法测试点）。
//   一个集合的合法测试点全体 W(S) 恒连通：若 x,z 合法，则 x-z 路径上任一点 u
//   对任意 y 有 dist(u,y) <= max(dist(x,y), dist(z,y))，故 u 也合法。
//   于是 W(S) 是 S 里的连通块，有唯一最浅点（以 0 为根）。按最浅点分类：
//     答案 = sum_x [ C(A_x, K) - C(C_x, K) ]
//   其中 C_x = #同时以 x 与其父亲为合法测试点的完美集合数（根处该项为 0）。
//   因为 K 个集合互不相同，这里的组合数是不放回的 C(·, K)；
//   K > A_x 时 C = 0。
//
// 【第二步：DFS 序背包求 A_x / C_x】
//   背包容量必须记「重量恰好为 c」而不是「<= c」，否则同价值、不同重量的集合
//   会在同一个状态上被合并而漏解。
//   把树按 DFS 序拍平：选 p_i 则转到 i+1；不选 p_i 则整棵子树都不能选，
//   直接跳到 i + size(p_i)。单次 O(N*M)。
//   求 C_x 时先强制选中 x 与父亲：把父亲安排成 x 的第一个孩子，强制点就落在
//   DFS 序的前缀上，可行域取 B_x ∩ B_{fa(x)}。
//
// 【第三步：C(n,K) mod 5^23】
//   模数是素数幂 5^23，n 可达 2^59，用手写的 Granville 型算法：
//     U(m) = prod_{i=1..m} (i 去掉所有因子 5 之后的部分) mod 5^23
//     C(n,K) = 5^(v5(n)-v5(K)-v5(n-K)) * U(n) * U(K)^-1 * U(n-K)^-1
//   指数 >= 23 时答案为 0。U(m) = U(m/5) * G(m)，其中
//     G(m) = prod_{i<=m, 5 不整除 i} i
//   而 prod_{j<t}(5j+r) 展开成以 5 为变量的幂级数，系数是初等对称多项式
//   e_k(0..t-1) = |s(t,t-k)|（第一类 Stirling 数），它关于 t 是 2k 次多项式，
//   用牛顿级数 sum c[k][i] * C(t,i) 求值；C(t,i)（i <= 46）直接剥掉阶乘里的
//   因子 5 再求逆元即可，避免预处理 5^23 规模的阶乘表。
#include <cstdio>
#include <cstring>
#include <cstdint>
#include <algorithm>
using namespace std;

typedef unsigned long long u64;
typedef long long ll;
typedef __int128 i128;

static const u64 MOD = 11920928955078125ULL;   // 5^23
static const int MAXN = 64;
static const int MAXM = 10005;

// ---------------- 组合数 mod 5^23 ----------------
static u64 mulmod(u64 a, u64 b) { return (u64)((i128)a * b % MOD); }

static u64 powmod(u64 a, u64 e) {
    u64 r = 1 % MOD; a %= MOD;
    while (e) { if (e & 1) r = mulmod(r, a); a = mulmod(a, a); e >>= 1; }
    return r;
}

// 模 5^23 下求逆（要求 a 与 5 互素），迭代版扩展欧几里得
static u64 exgcd(u64 a) {
    i128 old_r = (i128)(a % MOD), r = (i128)MOD, old_s = 1, s = 0;
    while (r != 0) {
        i128 q = old_r / r;
        i128 t = old_r - q * r; old_r = r; r = t;
        t = old_s - q * s; old_s = s; s = t;
    }
    i128 x = old_s % (i128)MOD;
    if (x < 0) x += (i128)MOD;
    return (u64)x;
}

static u64 mi5[32];
static u64 invSmall[64];        // i 去掉 5 因子后的逆元
static u64 newtonC[24][48];     // 牛顿级数系数
static u64 binomT[48];          // 当前 t 下 C(t,i) mod MOD

// C(t,m) mod MOD，m <= 46（t 可以任意大）
static u64 smallC(u64 t, int m) {
    if (m < 0) return 0;
    if (t < (u64)m) return 0;
    if (m == 0) return 1;
    int e = 0;
    u64 res = 1;
    for (int i = 1; i <= m; i++) {
        u64 x = t - m + i;
        while (x % 5 == 0) { x /= 5; e++; }
        res = mulmod(res, x % MOD);
    }
    for (int i = 1; i <= m; i++) {
        u64 x = i;
        while (x % 5 == 0) { x /= 5; e--; }
        res = mulmod(res, invSmall[i]);
    }
    if (e >= 23) return 0;
    return mulmod(res, mi5[e]);
}

static void initCombo() {
    mi5[0] = 1;
    for (int i = 1; i < 32; i++) mi5[i] = mi5[i - 1] * 5 % MOD;
    for (int i = 1; i <= 46; i++) {
        u64 x = i;
        while (x % 5 == 0) x /= 5;
        invSmall[i] = exgcd(x % MOD);
    }
    static u64 S[48][48];
    memset(S, 0, sizeof(S));
    S[0][0] = 1;
    for (int i = 1; i < 48; i++)
        for (int j = 1; j <= i; j++)
            S[i][j] = (u64)(((i128)S[i - 1][j - 1] + (i128)(i - 1) * S[i - 1][j] % MOD) % MOD);
    for (int k = 0; k <= 22; k++) {
        static u64 f[48];
        for (int t = 0; t < 48; t++) f[t] = (t - k >= 0) ? S[t][t - k] : 0;
        for (int i = 0; i <= 2 * k && i < 48; i++) {
            newtonC[k][i] = f[0];
            for (int t = 0; t + 1 < 48; t++) f[t] = (f[t + 1] + MOD - f[t]) % MOD;
        }
    }
}

static void buildBinomT(u64 t) {
    for (int i = 0; i <= 46; i++) binomT[i] = smallC(t, i);
}

static u64 elemSym(u64 t, int k) {
    u64 r = 0;
    int lim = 2 * k; if (lim > 46) lim = 46;
    for (int i = 0; i <= lim; i++)
        if (newtonC[k][i]) r = (r + mulmod(newtonC[k][i], binomT[i])) % MOD;
    return r;
}

static u64 prodArith(u64 t, int r) {
    u64 rt = powmod((u64)r, t);
    u64 ir = exgcd((u64)r);
    u64 res = 0, acc = 1;
    u64 lim = t < 23 ? t : 22;
    for (u64 k = 0; k <= lim; k++) {
        res = (res + mulmod(acc, mulmod(elemSym(t, (int)k), rt))) % MOD;
        acc = mulmod(acc, mulmod(5, ir));
    }
    return res;
}

static u64 Gfun(u64 m) {
    u64 t = m / 5, s = m % 5;
    buildBinomT(t);
    u64 res = 1;
    for (int r = 1; r <= 4; r++) res = mulmod(res, prodArith(t, r));
    u64 tm = mulmod(t % MOD, 5);
    for (u64 r = 1; r <= s; r++) res = mulmod(res, (tm + r) % MOD);
    return res;
}

static u64 Ufun(u64 m) {
    u64 res = 1;
    static u64 stk[64];
    int top = 0;
    while (m > 0) { stk[top++] = m; m /= 5; }
    while (top > 0) res = mulmod(res, Gfun(stk[--top]));
    return res;
}

static u64 v5fact(u64 n) { u64 s = 0; while (n) { n /= 5; s += n; } return s; }

// 组合数 C(n,K) mod 5^23
static u64 combination(u64 n, u64 K) {
    if (K > n) return 0;
    if (K == 0) return 1;
    u64 e = v5fact(n) - v5fact(K) - v5fact(n - K);
    if (e >= 23) return 0;
    u64 un = Ufun(n), uk = Ufun(K), ur = Ufun(n - K);
    return mulmod(mi5[e], mulmod(mulmod(un, exgcd(uk)), exgcd(ur)));
}

// ---------------- 图 ----------------
static int N, M;
static ll  K, Max;
static ll  w[MAXN], v[MAXN];
static ll  dist_[MAXN][MAXN];
static int head_[MAXN], nxt_[2 * MAXN], to_[2 * MAXN], eCnt;
static ll  ew_[2 * MAXN];
static bool allowed_[MAXN];

static void addEdge(int a, int b, ll c) {
    to_[eCnt] = b; ew_[eCnt] = c; nxt_[eCnt] = head_[a]; head_[a] = eCnt++;
}

// ---------------- DFS 序 ----------------
static int order_[MAXN], tin_[MAXN], jump_[MAXN], parent_[MAXN];
static int fa_[MAXN];           // 以 0 为根的父亲数组（不会被 buildOrder 覆盖）

// 以 root 为根拍 DFS 序（递归深度 <= N = 60，安全）。
// firstChild >= 0 时，强制它成为 root 的第一个孩子，
// 这样 forced 里的点就落在 DFS 序的前缀 order_[0..flen-1] 上。
static int childL_[MAXN][MAXN], childN_[MAXN];

static void buildOrder(int root, int firstChild) {
    // 先按无向图重新求每个点在 root 下的孩子列表
    static int stk[MAXN];
    static bool vis[MAXN];
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < N; i++) childN_[i] = 0;
    int top = 0; stk[top++] = root; vis[root] = true; parent_[root] = -1;
    while (top > 0) {
        int u = stk[--top];
        for (int e = head_[u]; e != -1; e = nxt_[e]) {
            int to = to_[e];
            if (vis[to]) continue;
            vis[to] = true;
            parent_[to] = u;
            childL_[u][childN_[u]++] = to;
            stk[top++] = to;
        }
    }
    // 把 firstChild 换到 root 孩子列表的第一位
    if (firstChild >= 0 && childN_[root] > 0) {
        int pos = -1;
        for (int i = 0; i < childN_[root]; i++) if (childL_[root][i] == firstChild) { pos = i; break; }
        if (pos > 0) { int t = childL_[root][0]; childL_[root][0] = childL_[root][pos]; childL_[root][pos] = t; }
    }
    // 迭代式 DFS（显式栈），保持孩子顺序
    static int sNode[MAXN], sIdx[MAXN];
    int cnt = 0;
    sNode[0] = root; sIdx[0] = 0; top = 0;
    tin_[root] = cnt; order_[cnt++] = root;
    while (top >= 0) {
        int u = sNode[top];
        if (sIdx[top] < childN_[u]) {
            int c = childL_[u][sIdx[top]++];
            tin_[c] = cnt; order_[cnt++] = c;
            top++; sNode[top] = c; sIdx[top] = 0;
        } else {
            jump_[u] = cnt;
            top--;
        }
    }
}

// ---------------- 背包 ----------------
// 注意：方案数不能取模！C(A_x, K) 依赖 A_x 的精确值（其 5 进制展开），
// 而连通块个数最多 2^59 + 59，用 unsigned long long 精确保存。
static ll  dpVal[MAXN][MAXM];
static u64 dpCnt[MAXN][MAXM];
static int Vstar;

// 「必选 forced[0..flen-1]、只能选 allowed_ 内的点、连通」时价值恰为 Vstar 的方案数
static u64 countWays(int root, const int *forced, int flen) {
    buildOrder(root, flen > 1 ? forced[1] : -1);
    int n = N;
    for (int c = 0; c <= M; c++) { dpVal[n][c] = -1; dpCnt[n][c] = 0; }
    dpVal[n][0] = 0; dpCnt[n][0] = 1;
    for (int i = n - 1; i >= 0; i--) {
        int u = order_[i];
        for (int c = 0; c <= M; c++) {
            ll bv = dpVal[jump_[u]][c];
            u64 bc = dpCnt[jump_[u]][c];
            if (allowed_[u] && w[u] <= c && dpVal[i + 1][c - (int)w[u]] >= 0) {
                ll cv = dpVal[i + 1][c - (int)w[u]] + v[u];
                u64 cc = dpCnt[i + 1][c - (int)w[u]];
                if (cv > bv) { bv = cv; bc = cc; }
                else if (cv == bv) { bc = bc + cc; }          // 精确计数，不取模
            }
            dpVal[i][c] = bv; dpCnt[i][c] = bc;
        }
    }
    int cap = M; ll addv = 0;
    for (int i = 0; i < flen; i++) {
        int u = forced[i];
        if (!allowed_[u] || w[u] > cap) return 0;
        cap -= (int)w[u]; addv += v[u];
    }
    ll best = -1; u64 tot = 0;
    for (int c = 0; c <= cap; c++) {
        if (dpVal[flen][c] < 0) continue;
        ll tv = dpVal[flen][c] + addv;
        if (tv > best) { best = tv; tot = dpCnt[flen][c]; }
        else if (tv == best) { tot = tot + dpCnt[flen][c]; }   // 精确计数
    }
    return (best == Vstar) ? tot : 0;
}

// 求最大点权和 V*
static void computeVstar() {
    int best = -1;
    for (int r = 0; r < N; r++) {
        for (int y = 0; y < N; y++) allowed_[y] = true;
        if (w[r] > M) continue;
        buildOrder(r, -1);
        int n = N;
        for (int c = 0; c <= M; c++) dpVal[n][c] = -1;
        dpVal[n][0] = 0;
        for (int i = n - 1; i >= 0; i--) {
            int u = order_[i];
            for (int c = 0; c <= M; c++) {
                ll bv = dpVal[jump_[u]][c];
                if (w[u] <= c && dpVal[i + 1][c - (int)w[u]] >= 0)
                    bv = max(bv, dpVal[i + 1][c - (int)w[u]] + v[u]);
                dpVal[i][c] = bv;
            }
        }
        int cap = M - (int)w[r]; ll addv = v[r];
        for (int c = 0; c <= cap; c++)
            if (dpVal[1][c] >= 0) best = max(best, (int)(dpVal[1][c] + addv));
    }
    Vstar = best;
}

int main() {
    initCombo();

    if (scanf("%d %d %lld %lld", &N, &M, &K, &Max) != 4) return 0;
    for (int i = 0; i < N; i++) scanf("%lld", &w[i]);
    for (int i = 0; i < N; i++) scanf("%lld", &v[i]);
    eCnt = 0;
    for (int i = 0; i < N; i++) head_[i] = -1;
    for (int i = 0; i < N - 1; i++) {
        int a, b; ll c;
        scanf("%d %d %lld", &a, &b, &c);
        a--; b--;
        addEdge(a, b, c); addEdge(b, a, c);
    }

    const ll INF = (ll)4e18;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) dist_[i][j] = (i == j ? 0 : INF);
    for (int u = 0; u < N; u++)
        for (int e = head_[u]; e != -1; e = nxt_[e]) {
            int to = to_[e];
            if (ew_[e] < dist_[u][to]) dist_[u][to] = ew_[e];
        }
    for (int k = 0; k < N; k++)
        for (int i = 0; i < N; i++) {
            if (dist_[i][k] == INF) continue;
            for (int j = 0; j < N; j++)
                if (dist_[i][k] + dist_[k][j] < dist_[i][j])
                    dist_[i][j] = dist_[i][k] + dist_[k][j];
        }

    computeVstar();
    if (Vstar < 0) { puts("0"); return 0; }

    // 以 0 为根的父亲数组（单独算一次，存进 fa_，不要被后面的 buildOrder 覆盖）
    for (int r = 0; r < N; r++) allowed_[r] = true;
    buildOrder(0, -1);
    for (int i = 0; i < N; i++) fa_[i] = parent_[i];

    u64 ans = 0;
    for (int x = 0; x < N; x++) {
        // A_x：x ∈ S ⊆ B_x
        for (int y = 0; y < N; y++)
            allowed_[y] = !(v[y] > 0 && dist_[x][y] > Max / v[y]) &&
                          (v[y] == 0 || dist_[x][y] * v[y] <= Max);
        if (!allowed_[x]) continue;      // 不可能，dist(x,x)=0 使得 x 一定合法
        int forced[2] = { x, -1 };
        u64 Ax = countWays(x, forced, 1);
        ans = (ans + combination(Ax, (u64)K)) % MOD;

        // C_x：x 与父亲同时合法
        int p = fa_[x];
        if (p == -1) continue;
        for (int y = 0; y < N; y++) {
            bool ok1 = (v[y] == 0 || dist_[x][y] * v[y] <= Max);
            bool ok2 = (v[y] == 0 || dist_[p][y] * v[y] <= Max);
            allowed_[y] = ok1 && ok2;
        }
        if (!allowed_[x] || !allowed_[p]) { /* 交集为空则 C=0 */ }
        else {
            forced[0] = x; forced[1] = p;
            u64 Cx = countWays(x, forced, 2);
            ans = (ans + MOD - combination(Cx, (u64)K)) % MOD;
        }
    }
    printf("%llu\n", ans);
    return 0;
}

    复杂度

    • 树形预处理（最短路、DFS 序）：O(N3)O(N^3) 或 O(N(N+E)log⁡N)O(N(N+E)\log N)。
    • 背包：V\*V^\*、NN 个 AxA_x、N−1N-1 个 CxC_x，共 O(N)O(N) 次 O(NM)O(NM)，总 O(N2M)≈3.6×107O(N^2M)\approx3.6\times10^7。
    • 组合数：O(Nlog⁡5n)O(N\log_5 n)，可忽略。
    • 空间：背包两维 O(NM)O(NM)，最短路 O(N2)O(N^2)，均在限制内。

    总结

    这道题由三层拼成，任何一层写错都会在样例之后暴露：

    • 树结构层：合法测试点集合 W(S)W(S) 恒连通（树度量的投影性质），于是「存在公共测试点」可以按交集中最浅的那个点分解，答案化成 ∑x[(AxK)−(CxK)]\sum_x[\binom{A_x}{K}-\binom{C_x}{K}]。
    • 背包层：DFS 序跳步把「含指定点的连通块」计数做到 O(NM)O(NM)。两个要害：容量记重量恰好为 cc（否则同价值不同重量的集合被合并漏解）；方案数不取模、用 u64 精确保存（因为组合数依赖 AxA_x 的精确值，而连通块个数最多 259+592^{59}+59 恰好放得下）。
    • 数论层：(nK) mod 523\binom{n}{K}\bmod 5^{23} 用剥因子 55 的 U(m)U(m) 函数，只对 55-free 部分求逆，规避了模数不是素数、又无法预处理 5235^{23} 阶乘的困难。
    • 边界：组合数是不放回的（选出 KK 个互不相同集合）；K>AxK>A_x 或 K>∣P∣K>|\mathcal P| 时对应项为 00；v5(nK)≥23v_5\binom{n}{K}\ge 23 时组合数为 00。