20200407 树

题意转化

将一棵树剖分为若干个颜色不同的联通块，求数目。

题解

这种题目第一反应就是树形dp，但是由于涉及到联通块，所以应当和 dfs 序有一定的关系。

dfs 序可以将一个树形结构映射到一个序列上，从而实现一些操作。

树链剖分就是按照特定的顺序对树进行 dfs 序标定，之后通过如线段树之类的数据结构进行维护完成的。

此外，通过入栈出栈都记录的 dfs 序，可以实现求 LCA 。

设 代表在 dfs 序上前 个点，使用 种颜色染色的方案数。

考虑 有两种获得贡献的来源：

  • 一是和父亲涂一样的颜色
  • 二是自己新开一种颜色

得到方程如下： 。

边界是 。

答案为

Code

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

typedef long long LL;

const int maxn = 300 + 7;
const int maxm = 600 + 7;
const int mod = 1000000007;

int n, k;
int Head[maxn], to[maxm], Next[maxm], tot;
LL dp[maxn][maxn];

void addedge(int x, int y) {
    to[++tot] = y, Next[tot] = Head[x], Head[x] = tot;
}
void add(int x, int y) {
    addedge(x, y);
    addedge(y, x);
}

template < typename Tp >
void read(Tp &x) {
    x = 0; int fh = 1; char ch = 1;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if(ch == '-') fh = -1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    x *= fh;
}

void Init(void) {
    read(n); read(k);
    for(int i = 1, x, y; i < n; i++) {
        read(x); read(y);
        add(x, y);
    }
}

void Work(void) {
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= k; j++) {
            dp[i][j] = (dp[i - 1][j] + (dp[i - 1][j - 1]*(k - j + 1))) % mod;
        }
    }
    LL ans = 0;
    for(int i = 1; i <= k; i++) ans = (ans + dp[n][i]) % mod;
    printf("%lld\n",ans);
}


int main(void) {
    Init();
    Work();
    return 0;
}