牛客练习赛1-B-树题解

系统管理员 2022-12-28 12:45 107阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入描述
     *  输出描述
     *  输入
     *  输出
     *  备注
 *  算法分析
 *  解题代码

--------------------

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

# 题目描述 #

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

## 输入描述 ##

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

## 输出描述 ##

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

## 输入 ##

4 3
    1 2
    2 3
    2 4

## 输出 ##

## 备注 ##

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

# 算法分析 #

题目的结果与树的形态无关， 一个点染上什么颜色是和前一个点相关。

一道简单的dp问题

**dp状态转移方程：**

*  **如果第i个点与第i-1个点的颜色相同，那么染色方案数相同，即dp\[i\]\[j\] = dp\[i - 1\]\[j\]**
 *  **如果第i个点与第i-1个点的颜色不同，那么就是去除这个颜色以外的j-1种颜色在第i-1点的方案数以及第i个点的颜色的方案数，即dp\[i\]\[j\] = d\[i - 1\]\[j - 1\] \* (k - (j - 1))**
 *  **因此方程为：dp\[i\]\[j\] = dp\[i - 1\]\[j\] + d\[i - 1\]\[j - 1\] \* (k - (j - 1))**

# 解题代码 #

#include <iostream>
    using namespace std;
    
    typedef long long ll;
    const ll mode = 1e9 + 7;
    ll dp[305][305];
    
    int main()
    {
        
        int n,k;
        
        cin >> n >> k;
        
        for(int i = 0; i < n - 1; i++){
        
            int a,b;
            cin >> a >> b;
        }
        
        //dp含义：前i个节点用j种颜色填充的方案数
        dp[0][0] = 1;   //前0个节点用0个颜色填充，就一种方案
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= k; j++){
        
                //如果第i个点与第i-1个点的颜色相同，那么方案数相同，即dp[i][j] = dp[i - 1][j]
              	//如果第i个点与第i-1个点的颜色不同，那么就是去除这个颜色以外的j-1种颜色在第i-1点的方案数						//以及第i个点的颜色的方案数，即dp[i][j] = d[i - 1][j - 1] * (k - (j - 1))
              	//所以一个点i的方案数为：dp[i][j] = dp[i - 1][j] + d[i - 1][j - 1] * (k - (j - 1))
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * (k - j + 1);
                dp[i][j] %= mode;
            }
        
      	//因为最多k个颜色，那么就可以用1～k种颜色去填充
      	//那么方案数就是1～k种颜色的结果总和
        ll ans = 0;
        for(int i = 1; i <=k; i++)
            ans = (ans + dp[n][i]) % mode;
        
        cout << ans << endl;
        
        return 0;
    }