【每日一题】dfs序/DP

https://ac.nowcoder.com/acm/problem/13611
shy有一颗树，树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的，当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同。请统计方案数。
题目：给k个联通块染色

学习到了~
树转换为线性结构————在对树进行深度优先遍历时把进(出)栈序列记录下来，记录下来的这个序列称为dfs序；
由深度优先遍历的性质知道，

• 对于一个节点，他的祖先节点肯定比他先进栈；
• 序列中两个节点编号相同夹着的序列就是这个节点的子树序列。

但是这道题。。。不关心dfs序具体是啥样。。。因为涂一个点只有两种选择，1.涂之前用过的颜色,只能涂父亲颜色（不关心父亲是谁，有父亲就只能涂一个）；2.涂之前没用过的颜色，只关心之前涂了颜***r>那么状态和选择都知道了：设dp[i][j]为前i个节点从k种颜色中取j种颜色取染色的方案数，则状态转移方程为：
比如k=5,dp[1][1]是前1个节点选1种颜色来涂，就是k-(j-1)=5种涂法
j>i的时候方法数都为0； 其实就是A(5,2)
代码：
dp做法

#include <bits/stdc++.h>
using namespace std;
const int maxn=305;
const int MOD = 1e9+7;
#define ll long long
ll dp[maxn][maxn];//

int main()
{
    int n;
    int k;
    cin>>n>>k;
    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)));
            dp[i][j] %= MOD;
        }
    }

    ll ans = 0;

    for(int i = 1;i <= k;i ++)
        ans = (ans + dp[n][i])%MOD;

    printf("%lld\n",ans);

    return 0;
}

组合原理做法
参考https://blog.nowcoder.net/n/e51124f462ab43baa6d9f356b07f4b63
我们可以从[1,k]枚举联通块的数量然后求出每种联通块能够染色方案数，因为方案数与顺序有关所以用排列，从一棵树中枚举联通块就是组合问题，然后乘法原理即可。
对于n个节点的树来说，联通块为i个的数量为C(n - 1, i - 1)；用k种颜色去染i个联通块就是A(k,i)
答案就是

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

typedef long long int ll;
ll mod = 1e9 + 7;
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a = (a*a)%p;b >>= 1;}return ans%p;}
ll Inv(ll x)          { return qp(x,mod-2,mod);}
ll C(ll n,ll m){if (m>n) return 0;ll ans = 1;for (int i = 1; i <= m; ++i) ans=ans*Inv(i)%mod*(n-i+1)%mod;return ans%mod;}
ll A(ll n,ll m,ll mod){ll sum=1; for(int i=n;i>=n-m+1;i--) sum=(sum*i)%mod; return sum%mod;}

void solved(){
    ll n,k;cin>>n>>k;
    ll ans = 0;
    for(int i = 1; i <= k; i++){
        ans += (C(n - 1, i - 1)%mod * A(k,i,mod) % mod)%mod;
    }
    cout<<ans % mod<<endl;
}
int main(){
    solved();
    return 0;
}