第十三章lca B-树 dfn序 线性DP()

 链接：https://ac.nowcoder.com/acm/contest/27836/B来源：牛客网

题目描述

输入描述:

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

输出描述:

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

输入

4 3
1 2
2 3
2 4

输出

39

备注:

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

分析

按照题目所说，所有颜色相等的两个节点之间的所有节点颜色相等

很容易想到dfn序里一个区间内颜色相等。

思考这颗树，可以想到如果一个新的节点颜色和之前的节点相等的话，那这个节点也必然和这个节点的根节点颜色相等

所以每个新的节点它的颜色要么和它的根节点颜色相等，要么和之前所有节点的颜色都不相等。

这样考虑最后一个点的问题，很容易想到线性DP。

设dp[i][j] 表示前i 个点，已经有了j 种颜色

dp[i][j] = d[i-1][j] + dp[i-1][j-1] * (k – 1 + 1) ;; 第i个节点要么和前面所有节点颜色相等（不出现新的颜色），要么与前面所有节点的颜色不相等（前面有j – 1 种颜色，当前节点有(k – j + 1）种可能）

建成一颗树只是迷惑，关键还是要把顺序理清楚，搞清楚关键点是根节点。

//-------------------------代码----------------------------

//#define int ll
const int N = 2e6+10,mod = 1e9+7;
int n,m,k;
ll f[500][500];

void solve()
{
//    cin>>n>>m;
    cin>>n>>k;
    fo(i,1,n-1)cin>>m>>m;
    f[0][0] = 1;
    fo(i,1,n) {
        of(j,k,1) {
//         fo(j,1,k) {
                f[i][j] = (f[i-1][j] + f[i-1][j-1] * (k - j + 1)) % mod;
        }
    }
    ll sum = 0;
    fo(i,1,k) {
        sum = (sum + f[n][i]) % mod;
//         fo(j,1,k) {
//             cout<<f[i][j]<<' ';
//         } cout<<endl;
    }
//     cout<<f[n][k]<<endl;
    cout<<sum % mod<<endl;
}

signed main(){
    AC();
    clapping();TLE;
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
//    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------
————————

 链接：https://ac.nowcoder.com/acm/contest/27836/B来源：牛客网

题目描述

输入描述:

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

输出描述:

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

输入

4 3
1 2
2 3
2 4

输出

39

备注:

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

分析

按照题目所说，所有颜色相等的两个节点之间的所有节点颜色相等

很容易想到dfn序里一个区间内颜色相等。

思考这颗树，可以想到如果一个新的节点颜色和之前的节点相等的话，那这个节点也必然和这个节点的根节点颜色相等

所以每个新的节点它的颜色要么和它的根节点颜色相等，要么和之前所有节点的颜色都不相等。

这样考虑最后一个点的问题，很容易想到线性DP。

设dp[i][j] 表示前i 个点，已经有了j 种颜色

dp[i][j] = d[i-1][j] + dp[i-1][j-1] * (k – 1 + 1) ;; 第i个节点要么和前面所有节点颜色相等（不出现新的颜色），要么与前面所有节点的颜色不相等（前面有j – 1 种颜色，当前节点有(k – j + 1）种可能）

建成一颗树只是迷惑，关键还是要把顺序理清楚，搞清楚关键点是根节点。

//-------------------------代码----------------------------

//#define int ll
const int N = 2e6+10,mod = 1e9+7;
int n,m,k;
ll f[500][500];

void solve()
{
//    cin>>n>>m;
    cin>>n>>k;
    fo(i,1,n-1)cin>>m>>m;
    f[0][0] = 1;
    fo(i,1,n) {
        of(j,k,1) {
//         fo(j,1,k) {
                f[i][j] = (f[i-1][j] + f[i-1][j-1] * (k - j + 1)) % mod;
        }
    }
    ll sum = 0;
    fo(i,1,k) {
        sum = (sum + f[n][i]) % mod;
//         fo(j,1,k) {
//             cout<<f[i][j]<<' ';
//         } cout<<endl;
    }
//     cout<<f[n][k]<<endl;
    cout<<sum % mod<<endl;
}

signed main(){
    AC();
    clapping();TLE;
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
//    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------