题意

• 给定一棵树，n个节点，你有k种颜色，对于任意相同颜色的点对，两个点之间的路径必须都和这两个点颜色相同，统计合法的染色方案个数

思路

• 由于树是连通的，所以如果要满足条件，一个节点的颜色要不然是一个全新的无人使用的颜色，要不然和自己的父亲相同
• 计数，考虑dp， 表示前i个节点使用了j种颜色，转移方程

代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
ll dp[400][400];
vector<int> G[500];
const int p=1e9+7;
int main(){
    int n,k;
    cin >> n >> k;
    for(int i=0;i<n;i++){
        int x,y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    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-1]*(k-(j-1)))%p+dp[i-1][j]%p;
        }
    }
    ll ans=0;
    for(int i=1;i<=k;i++){
        ans=(ans+dp[n][i])%p;
    }
    cout << ans << endl;
    return 0;
}