问题分析

我们需要在树上选择恰好 $M$ 个节点，使得：

1. 选择的节点集合是一个独立集（相邻节点不能同时被选）
2. 计算所有合法选择方案的美丽值乘积之和

这是一个典型的树形独立集计数问题，但需要计算带权和的生成函数。

关键观察

对于每个节点 $x$，我们定义两个状态：

• $f_0[x]$：不选择节点 $x$ 时的生成函数
• $f_1[x]$：选择节点 $x$ 时的生成函数

其中生成函数 $F(x) = \sum_{i=0}^n a_i x^i$ 表示选择 $i$ 个节点的所有方案权值和。

算法思路

1. 树链剖分优化

使用树链剖分将树分解为重链，在重链上使用分治FFT进行高效合并：

• 第一次DFS计算子树大小、父节点、重儿子
• 第二次DFS在重链上使用分治策略合并DP值

2. 状态转移方程

对于节点 $x$：

• 如果不选 $x$，那么它的所有儿子节点可选可不选：

  $$f_0[x] = \prod_{v \in \text{sons}(x)} (f_0[v] + f_1[v]) $$

• 如果选 $x$，那么它的所有儿子节点都不能选：

  $$f_1[x] = b_x \cdot x \cdot \prod_{v \in \text{sons}(x)} f_0[v] $$

其中 $b_x$ 是节点 $x$ 的美丽值，$x$ 是生成函数的形式变量。

3. 重链上的合并

在重链上，使用分治FFT来合并DP值。对于重链上的节点序列 $u_1, u_2, \ldots, u_k$，我们定义：

• $g_0[i]$：考虑前 $i$ 个节点，不选 $u_i$ 的生成函数
• $g_1[i]$：考虑前 $i$ 个节点，选 $u_i$ 的生成函数

转移方程为：

$$\begin{aligned} g_0[i] &= g_0[i-1] \cdot (f_0[u_i] + f_1[u_i]) + g_1[i-1] \cdot f_0[u_i] \\ g_1[i] &= g_0[i-1] \cdot f_1[u_i] \end{aligned} $$

这个转移可以用矩阵形式表示，并在重链上使用分治FFT快速计算。

核心算法实现

1. FFT/NTT 实现

vector<int> FFT(const vector<int> &val, int tot, int lgt, vector<int> *base = bg) {
    vector<int> res(tot);
    for (int j = 0; j < tot; j++) {
        if (trs[lgt][j] < val.size()) {
            res[j] = val[trs[lgt][j]];
        }
    }
    for (int i = 1; i <= lgt; i++) {
        int len = 1 << i;
        int hlen = len / 2;
        for (int j = 0; j < tot; j += len) {
            for (int k = j; k < j + hlen; k++) {
                int va = res[k], vb = 1ll * base[i][k - j] * res[k + hlen] % MOD;
                res[k] = (va + vb) % MOD;
                res[k + hlen] = (va - vb + MOD) % MOD;
            }
        }
    }
    return res;
}

2. 重链上的分治合并

vector<vector<vector<int>>> calc(const vector<int> &ids, int l, int r) {
    if (l == r) {
        return { { f[0][ids[l]], { 0 } }, { { 0 }, f[1][ids[l]] } };
    }
    int mid = (l + r) / 2;
    auto r1 = calc(ids, l, mid);
    auto r2 = calc(ids, mid + 1, r);
    return { {
            (r1[0][0] * r2[1][0] % m + r1[0][1] * r2[0][0] % m + r1[0][0] * r2[0][0] % m) % m,
            (r1[0][0] * r2[1][1] % m + r1[0][1] * r2[0][1] % m + r1[0][0] * r2[0][1] % m) % m
        },
        {
            (r1[1][0] * r2[1][0] % m + r1[1][1] * r2[0][0] % m + r1[1][0] * r2[0][0] % m) % m,
            (r1[1][0] * r2[1][1] % m + r1[1][1] * r2[0][1] % m + r1[1][0] * r2[0][1] % m) % m
        } };
}

3. 主要DFS过程

void dfs2(int x, int tf) {
    vector<vector<int>> p1(1, { 1 }), p2(1, { 0, b[x] });
    
    // 处理轻儿子
    for (int v : bian[x]) {
        if (v == fath[x] || v == son[x]) continue;
        dfs2(v, v);
        p1.push_back(f[1][v] + f[0][v]);
        p2.push_back(f[0][v]);
    }
    
    // 合并轻儿子的贡献
    f[0][x] = mul(p1, 0, p1.size() - 1);
    f[1][x] = mul(p2, 0, p2.size() - 1);
    
    // 处理重链
    if (!son[x]) {
        vector<int> ids;
        int cur = x;
        while (x != fath[tf]) {
            ids.push_back(x);
            x = fath[x];
        }
        auto r = calc(ids, 0, ids.size() - 1);
        f[0][tf] = r[0][0] + r[1][0];
        f[1][tf] = r[0][1] + r[1][1];
        return;
    }
    dfs2(son[x], tf);
}

复杂度分析

• FFT/NTT 卷积：$O(n \log n)$
• 树链剖分：每条重链上的分治FFT复杂度为 $O(n \log^2 n)$
• 总复杂度：$O(n \log^3 n)$

算法优势

1. 高效性：利用树链剖分和分治FFT，将复杂度优化到 $O(n \log^3 n)$
2. 通用性：适用于任意树形结构
3. 正确性：基于独立的组合数学原理，状态转移清晰

代码总结

本题通过结合树链剖分、生成函数和分治FFT，高效解决了树上带权独立集计数问题。算法充分利用了树的特殊结构和多项式卷积的性质，实现了在大数据规模下的高效计算。

该解法能够处理 $n \leq 8 \times 10^4$ 的数据规模，适用于所有 Subtask，是解决此类问题的标准且高效的方案。