題干：
?

shy有一顆樹，樹有n個結點。有k種不同顏色的染料給樹染色。一個染色方案是合法的，當且僅當對于所有相同顏色的點對(x,y)，x到y的路徑上的所有點的顏色都要與x和y相同。請統計方案數。

輸入描述:

第一行兩個整數n，k代表點數和顏色數； 接下來n-1行，每行兩個整數x,y表示x與y之間存在一條邊；

輸出描述:

輸出一個整數表示方案數（mod 1e9+7）。

示例1

輸入

復制

4 3 1 2 2 3 2 4

輸出

復制

39

備注:

對于30%的數據，n≤10, k≤3； 對于100%的數據，n,k≤300。

解題報告：

一句話題解：因為樹上的任意兩個點都是可以兩兩聯通的，而染色的過程就是構造聯通快的過程，即將一顆樹拆分成若干子樹。

? ?其實分析一下就是求個連通塊（每一個子樹都當成一個連通塊，最后然你求構成連通塊的方案數，，所以這題邊的讀入根本無所謂，我們不去關心，，因為就算樹不是同一種狀態，，但是因為染色使用的顏色數和每種顏色對應染的節點數只要相同，我們就認為是一種相同的方案。）

dp[i][j]表示用i個點染j種顏色的方案數。狀態轉移：選擇新開一個顏色，或者和上一個節點用一個顏色（也就是：在一個連通塊內，不在一個連通塊內。）

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; const ll mod = 1e9+7; ll dp[505][505]; int main() {int n,k;cin>>n>>k;for(int a,b,i = 1; i<=n-1; i++) {scanf("%d%d",&a,&b);} for(int i = 1; i<=n; i++) {for(int j = 1; j<=k; j++) {if(i==1 &&j==1) dp[i][j]=k;else dp[i][j] = (dp[i-1][j] + dp[i-1][j-1] * (k-(j-1)))%mod;}}ll ans = 0;for(int j = 1; j<=k; j++) {ans = (ans + dp[n][j])%mod;}printf("%lld\n",ans);return 0 ;}

?

總結

以上是生活随笔為你收集整理的【牛客 - 2B】树（思维，dp，有坑）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。