Leader in Tree Land
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 447 Accepted Submission(s): 185
Problem Description
Tree land has n cities, connected by n−1 roads. You can go to any city from any city. In other words, this land is a tree. The city numbered one is the root of this tree.
There are n ministers numbered from 1 to n. You will send them to n cities, one city with one minister.
Since this is a rooted tree, each city is a root of a subtree and there are n subtrees. The leader of a subtree is the minister with maximal number in this subtree. As you can see, one minister can be the leader of several subtrees.
One day all the leaders attend a meet, you find that there are exactly k ministers. You want to know how many ways to send n ministers to each city so that there are k ministers attend the meet.
Give your answer mod $1000000007$.
Input
Multiple test cases. In the first line there is an integer T, indicating the number of test cases. For each test case, first line contains two numbers n,k. Next n−1 line describe the roads of tree land.
$T=10,1 leq n leq 1000,1 leq k leq n$
Output
For each test case, output one line. The output format is Case #x: ans, x is the case number,starting from 1.
Sample Input
2
3 2
1 2
1 3
10 8
2 1
3 2
4 1
5 3
6 1
7 3
8 7
9 7
10 6
Sample Output
Case #1: 4
Case #2: 316512
Author
UESTC
Source
2015 Multi-University Training Contest 7 1010
解题：动态规划 这位博主大牛说得非常清楚
我们用x[i],y[i]分别代表这个节点能够成为leader和不能够成为leader的概率。
son[i] 代表以i节点为根的子树的节点数。
那么$x[i] = 1/son[i]，y[i] = 1-(1/son[i])$。因为这里面出现了分数，所有我们用逆元处理一下。
我们设dp[i][j]表示编号为1,2...i的节点中有j个leader的概率。
那么转移方程就是 $dp[i][j] = dp[i-1][j-1] * x[i] + dp[i-1][j] * y[i]$。
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const LL mod = 1000000007; 5 const int maxn = 1010; 6 struct arc { 7 int to,next; 8 arc(int x = 0,int y = -1) { 9 to = x; 10 next = y; 11 } 12 } e[maxn<<1]; 13 int son[maxn],head[maxn],tot; 14 LL F[maxn] = {1},x[maxn],y[maxn],dp[maxn][maxn]; 15 void init() { 16 for(int i = 1; i < maxn; ++i) 17 F[i] = F[i-1]*i%mod; 18 } 19 void add(int u,int v) { 20 e[tot] = arc(v,head[u]); 21 head[u] = tot++; 22 } 23 LL gcd(LL a,LL b,LL &x,LL &y) { //ax + by = gcd(a,b) 24 if(!b) { 25 x = 1; 26 y = 0; 27 return a; 28 } 29 LL ret = gcd(b,a%b,y,x); 30 y -= x*(a/b); 31 return ret; 32 } 33 LL Inv(LL b,LL mod) { //求b % mod的逆元 34 LL x,y,d = gcd(b,mod,x,y); 35 return d == 1?(x%mod + mod)%mod:-1; 36 } 37 void dfs(int u,int fa) { 38 son[u] = 1; 39 for(int i = head[u]; ~i; i = e[i].next) { 40 if(e[i].to == fa) continue; 41 dfs(e[i].to,u); 42 son[u] += son[e[i].to]; 43 } 44 } 45 int main() { 46 int kase,n,k,u,v,cs = 1; 47 init(); 48 scanf("%d",&kase); 49 while(kase--) { 50 scanf("%d%d",&n,&k); 51 memset(head,-1,sizeof head); 52 tot = 0; 53 for(int i = 1; i < n; ++i) { 54 scanf("%d%d",&u,&v); 55 add(u,v); 56 add(v,u); 57 } 58 dfs(1,-1); 59 for(int i = 1; i <= n; ++i) { 60 x[i] = Inv(son[i],mod); 61 y[i] = (son[i] - 1)*x[i]%mod; 62 } 63 memset(dp,0,sizeof dp); 64 dp[1][0] = y[1]; 65 dp[1][1] = x[1]; 66 for(int i = 2; i <= n; ++i) { 67 dp[i][0] = dp[i-1][0]*y[i]%mod; 68 for(int j = 1; j <= min(i,k); ++j) { 69 LL a = dp[i-1][j-1]*x[i]%mod; 70 LL b = dp[i-1][j]*y[i]%mod; 71 dp[i][j] = (a + b)%mod; 72 } 73 } 74 printf("Case #%d: %I64d ",cs++,dp[n][k]*F[n]%mod); 75 } 76 return 0; 77 }