树

题意:给一棵树进行染色,并且要保证(x,y)成立,也就是从X节点到y节点的颜色相同
题解:因为题目没有对节点进行要求(虽然给定节点的边的关系)
此题看上去是一个染色，其实任意两个相同颜色的点对，之间都的一个颜色，那就是一个联通分量全是一个颜色。
树，就可以看做是一个点集合，挑哪些点染同一种颜色。显然是DP做法。

每一个点跟前一个点的关系只有颜色相同、颜色不同两种，当颜色相同时，该点的方案数等于上一个点方案数，当颜色不同时,只能使用剩余的 种颜色,所以

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
ll dp[500][500];
int main()
{
    int n, m;
    cin >> n >> m;
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            dp[i][j] = dp[i - 1][j - 1] * (m - j + 1);
            dp[i][j] = dp[i][j] % MOD;
            dp[i][j] += dp[i - 1][j];
            dp[i][j] = dp[i][j] % MOD;
        }
    }
    ll sum = 0;
    for(int i = 1; i <= m; i++)
    {
        sum += dp[n][i];
        sum = sum % MOD;
    }
    cout << sum <<endl;
    return 0;
}

本篇博客部分内容参考:https://www.cnblogs.com/TreeDream/p/7846372.html