树

题目意思是用k个点把一个有n个节点的树染色,然后的地方必须联通,求有多少方案数?
下面给大家介绍两种做法..

做法1:切边表示染色用的颜色个数,比如我要用3种颜色染色,那么我就只要考虑切2条边,比如切2-4,和3和7这是一种方案,那么,考虑树,一共n个点,一共n-1条边,我可以用k种颜色染色,那么就是切k-1条边.也就是选k-1条边.那么答案就是:
Cn-1 0+Cn-1 1+Cn-1 2+Cn-1 3+...+Cn-1 k-3+Cn-1 k-2+Cn-1 k-1的和..然后考虑染色,假如我现在切的是i条边,那么,我选颜色总数就是A(k,i+1). 代码如下:

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
#define inf 132913423039
typedef long long ll;
const ll mod=1e9+7;
const ll N=2e3+5;
const ll M=2e4+5;
const double eps=1e-7;
using namespace std;
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b) { return a*b/gcd(a,b);    }
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;}
int main()
{
     ios;
     ll n,k,ans=0,x,y;
     cin>>n>>k;
     for(int i=0;i<n-1;i++)  cin>>x>>y;
     for(ll i=0;i<k;i++)
     {
         ans=(ans+(A(k,i+1,mod)*C(n-1,i))%mod)%mod;
     }
     cout<<ans<<endl;
     return 0;
}

做法2:
用dp来做.设dp[i][j]表示我染色了i个用了j种颜***r>
考虑我现在已经到了dp[7][3]了,那我现在是不是可以到dp[8][3]/dp[8][4]去,到dp[8][3]是不是就等于dp[7][3],而dp[8][4]是不是就等于dp[7][3](还可以染的颜色种数)..那么就是dp[8][4]=dp[7][3](k-3)+还有一种就是dp[7][4]上个7个格子染色4个继续下一个..对吧..由此我们可以推出方程就是:
dp[i][j]=dp[i-1][j-1]*(k-(j-1))+dp[i-1][j];
代码如下:

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
#define inf 132913423039
typedef long long ll;
const ll mod=1e9+7;
const ll N=3e2+5;
const ll M=2e4+5;
const double eps=1e-7;
using namespace std;
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b) { return a*b/gcd(a,b);    }
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;}
ll dp[N][N];
int main()
{
     ios;
     ll n,k,x,y,ans=0;
     cin>>n>>k;
     for(int i=0;i<n-1;i++) cin>>x>>y;
     dp[0][0]=1;
     for(ll i=1;i<=n;i++)
     {
         for(ll j=1;j<=min(k,i);j++)
         {
             dp[i][j]=(dp[i-1][j]+dp[i-1][j-1]*(k-(j-1)%mod))%mod;
         }
     }
     for(ll i=1;i<=k;i++) ans=(ans+dp[n][i])%mod;
     cout<<ans<<endl;
     return 0;
}