NC13611 树

题目描述

shy有一颗树，树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的，当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同。请统计方案数。

输入描述:

第一行两个整数n，k代表点数和颜色数；
接下来n-1行，每行两个整数x,y表示x与y之间存在一条边；

输出描述:

输出一个整数表示方案数（mod 1e9+7）。

示例1

输入

4 3
1 2
2 3
2 4

输出

39

备注:

对于30%的数据，n≤10, k≤3；
对于100%的数据，n,k≤300。

分析

首先要观察一下相同颜色的点的性质，如图。

可以发现，一个点要么和它父亲颜色一样，要么自己新开一种没用过的颜色，没有多的情况了。
那么我们就可以考虑转移。
设 表示前 个点，用了 种颜色的方案数。
第 个点和父亲颜色一样：
第 个点新开一种没用过的颜色：
最后

代码如下

#include <bits/stdc++.h>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define N 305
using namespace __gnu_pbds;
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int mod = 1e9 + 7;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
LL z = 1;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
int ksm(int a, int b, int p){
    int s = 1;
    while(b){
        if(b & 1) s = z * s * a % p;
        a = z * a * a % p;
        b >>= 1;
    }
    return s;
}
int f[N][N], ans;
int main(){
    int i, j, n, m;
    n = read(); m = read();
    f[0][0] = 1;
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            f[i][j] = (f[i - 1][j] + z * f[i - 1][j - 1] * (m - j + 1) % mod) % mod;
        }
    }
    for(i = 1; i <= m; i++) ans = (ans + f[n][i]) % mod;
    printf("%d", ans);
    return 0;
}