牛客每日一题 4.7 树 树dp+组合数学

https://blog.csdn.net/qq_43804974/article/details/105345340
昨天的牛客鸽了，我不会数学

首先第一步要理解题意就是要把树分成多个联通块，每个联通块的颜色都要不一样，求方案数。
为什么每个联通块的颜色都不一样，因为如果有同样的颜色在不同的联通块上的话就无法满足题意，这两个点之间的路径的所有点就不会是都是同一种色。

用f[i][j]代表的是以i为根的子树分成j个联通块的的方案数。由于我没想到大佬说的分成j个联通块就是删掉j-1条边，所以就硬算去合并每个子树的答案。
暴力合并就复杂度变成n^3;

得到每种联通块的方案数后就是组合数学算一下就好了，有j个联通块，就是在k种色里选j个，然后在全排列

vector<int>xian[max_];
int f[max_][max_],n,k,cal[2][max_];
void dfs(int now, int fa) {
    for (auto to : xian[now]) {
        if (to == fa)continue;
        dfs(to, now);
    }
    memset(cal, 0, sizeof(cal));
    int last = 1;
    cal[0][1] = 1;
    for (auto to : xian[now]) {
        if (to == fa)continue;
        memset(cal[last], 0, sizeof(cal[last]));
        for (int i = 1; i <= k; i++) {
            for (int j = 1; j <= k; j++) {
                cal[last][i + j] += cal[last ^ 1][i] * f[to][j]; cal[last][i + j] %= mod;
                cal[last][i + j - 1] += cal[last ^ 1][i] * f[to][j]; cal[last][i + j - 1] %= mod;
            }
        }
        last ^= 1;
    }
    for (int i = 1; i <= k; i++) {
        f[now][i] = cal[last ^ 1][i];
    }
}
int value[max_];
signed main() {
    n = read(), k = read();
    for (int i = 2; i <= n; i++) {
        int a = read(), b = read();
        xian[a].push_back(b);
        xian[b].push_back(a);
    }
    dfs(1, 0);
    /*for (int i = 1; i <= k; i++) {
        cout << f[1][i] << endl;
    }*/
    value[1] = k;
    for (int i = 1; i <= 300; i++) {
        value[i + 1] = value[i] * (k - i);
        value[i + 1] %= mod;
    }
    int ans = 0;
    for (int i = 1; i <= k; i++) {
        ans += f[1][i] * value[i];
        ans %= mod;
    }
    //cout << endl;
    cout << ans;
    return 0;
}