HDU5378LeaderinTreeLand【树形DP】

第一种思路是最普遍的树形DP
dp[u][i]表示u这个节点以及下面的子树&＃xff0c;有i个leader的方案数。
首先&＃xff0c;我们考虑&＃xff0c;每棵子树上面的leader&＃xff0c;他们的个数是不会因为父亲节点的取值而减少的&＃xff0c;所以符合加法性质&＃xff0c;因此可以直接累加上去。于是可以用背包的方式直接累加上去。
其次&＃xff0c;要计算一次组合数&＃xff0c;和普通的树形DP相像&＃xff0c;从一开始可以分配Csz[v]sz[u]种方案&＃xff0c;可分配的颜色随着分配的子树逐渐减少。
最后&＃xff0c;考虑u这个节点的情况。分两种情况讨论&＃xff0c;u节点是leader&＃xff0c;那么就是从子树背包的numofleader−1的情况转移&＃xff0c;只有一种情况&＃xff1b;如果u节点不是leader&＃xff0c;那么就是从numofleader的情况转移&＃xff0c;但是有sz[u]−1种情况&＃xff0c;可以将这个模型理解成是插板法&＃xff1a;将子树的权值按顺序从小到大排列&＃xff0c;那么u的权值可以插在除了最后一位的所有位置&＃xff0c;共sz[u]−1种可能。

// whn6325689
// Mr.Phoebe
// http://blog.csdn.net/u013007900
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62
#define speed std::ios::sync_with_stdio(false);typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair pll;
typedef complex point;
typedef pair<int, int> pii;
typedef pairint> piii;
typedef vector<int> vi;#define CLR(x,y) memset(x,y,sizeof(x))
#define CPY(x,y) memcpy(x,y,sizeof(x))
#define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
#define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))#define MID(x,y) (x&＃43;((y-x)>>1))
#define ls (idx<<1)
#define rs (idx<<1|1)
#define lson ls,l,mid
#define rson rs,mid&＃43;1,r
#define root 1,1,ntemplate<class T>
inline bool read(T &n)
{T x &＃61; 0, tmp &＃61; 1;char c &＃61; getchar();while((c <&＃39;0&＃39; || c > &＃39;9&＃39;) && c !&＃61; &＃39;-&＃39; && c !&＃61; EOF) c &＃61; getchar();if(c &＃61;&＃61; EOF) return false;if(c &＃61;&＃61; &＃39;-&＃39;) c &＃61; getchar(), tmp &＃61; -1;while(c >&＃61; &＃39;0&＃39; && c <&＃61; &＃39;9&＃39;) x *&＃61; 10, x &＃43;&＃61; (c - &＃39;0&＃39;),c &＃61; getchar();n &＃61; x*tmp;return true;
}
template <class T>
inline void write(T n)
{if(n <0){putchar(&＃39;-&＃39;);n &＃61; -n;}int len &＃61; 0,data[20];while(n){data[len&＃43;&＃43;] &＃61; n%10;n /&＃61; 10;}if(!len) data[len&＃43;&＃43;] &＃61; 0;while(len--) putchar(data[len]&＃43;48);
}
//-----------------------------------const int MAXN&＃61;1010;
const int MOD&＃61;1e9&＃43;7;int n,K;struct Edge
{int to,next;
}e[MAXN<<1];
int head[MAXN],tot;
int sz[MAXN];
ll dp[MAXN][MAXN],ret[2][MAXN],C[MAXN][MAXN];void init()
{CLR(dp,0);CLR(head,-1);tot&＃61;0;
}void addedge(int u,int v)
{e[tot].to&＃61;v;e[tot].next&＃61;head[u];head[u]&＃61;tot&＃43;&＃43;;
}
void dfs(int u,int fa&＃61;-1)
{sz[u]&＃61;1;for(int i&＃61;head[u]; ~i; i&＃61;e[i].next){int v&＃61;e[i].to;if(v&＃61;&＃61;fa) continue;dfs(v,u);sz[u]&＃43;&＃61;sz[v];}ret[0][0]&＃61;1;int all&＃61;0,cur&＃61;0;for(int i&＃61;head[u]; ~i; i&＃61;e[i].next){int v&＃61;e[i].to;if(v&＃61;&＃61;fa) continue;for(int j&＃61;0; j<&＃61;min(K,all&＃43;sz[v]&＃43;1); j&＃43;&＃43;)ret[cur^1][j]&＃61;0;for(int j&＃61;min(K,all); j>&＃61;0; j--){if(!ret[cur][j]) continue;for(int k&＃61;1; k<&＃61;min(K,sz[v]); k&＃43;&＃43;){ret[cur^1][j&＃43;k]&＃43;&＃61;ret[cur][j]*dp[v][k]%MOD*C[sz[u]-1-all][sz[v]]%MOD;ret[cur^1][j&＃43;k]%&＃61;MOD;}}cur^&＃61;1;all&＃43;&＃61;sz[v];}for(int i&＃61;min(K,sz[u]); i>&＃61;1; i--){// printf("dp[%d][%d]&＃61;%I64d\n",v,i,ret[cur][i]);dp[u][i]&＃61;ret[cur][i]*(sz[u]-1)%MOD&＃43;ret[cur][i-1];dp[u][i]%&＃61;MOD;}
}
int main()
{C[0][0]&＃61;1;for(int i&＃61;1; i0]&＃61;C[i][i]&＃61;1;for(int j&＃61;1; j1][j-1]&＃43;C[i-1][j])%MOD;}int T,cas&＃61;1;read(T);while(T--){init();read(n),read(K);for(int i&＃61;0, u, v; i1; i&＃43;&＃43;){read(u),read(v);addedge(u,v);addedge(v,u);}dfs(1);printf("Case #%d: %I64d\n",cas&＃43;&＃43;,dp[1][K]);}return 0;
}


可以用求概率的思想来解决这个问题。令以i号节点为根的子树为第i棵子树&＃xff0c;设这颗子树恰好有sz[i]个点。那么第i个点是第i棵子树最大值的概率为1/sz[i]&＃xff0c;不是最大值的概率为(sz[i]−1)/sz[i]。现在可以求解恰好有k个最大值的概率。
令dp[i][j]表示考虑编号从1到i的点&＃xff0c;其中恰好有j个点是其子树最大值的概率。 很容易得到如下转移方程：dp[i][j]=dp[i−1][j]∗(sz[i]−1)/sz[i]+dp[i−1][j−1]/sz[i]。这样dp[n][k]就是所有点中恰好有k个最大值的概率。
题目要求的是方案数，用总数n！乘上概率就是答案。计算的时候用逆元代替上面的分数即可

// whn6325689
// Mr.Phoebe
// http://blog.csdn.net/u013007900
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62
#define speed std::ios::sync_with_stdio(false);typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair pll;
typedef complex point;
typedef pair<int, int> pii;
typedef pairint> piii;
typedef vector<int> vi;#define CLR(x,y) memset(x,y,sizeof(x))
#define CPY(x,y) memcpy(x,y,sizeof(x))
#define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
#define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))#define MID(x,y) (x&＃43;((y-x)>>1))
#define ls (idx<<1)
#define rs (idx<<1|1)
#define lson ls,l,mid
#define rson rs,mid&＃43;1,r
#define root 1,1,ntemplate<class T>
inline bool read(T &n)
{T x &＃61; 0, tmp &＃61; 1;char c &＃61; getchar();while((c <&＃39;0&＃39; || c > &＃39;9&＃39;) && c !&＃61; &＃39;-&＃39; && c !&＃61; EOF) c &＃61; getchar();if(c &＃61;&＃61; EOF) return false;if(c &＃61;&＃61; &＃39;-&＃39;) c &＃61; getchar(), tmp &＃61; -1;while(c >&＃61; &＃39;0&＃39; && c <&＃61; &＃39;9&＃39;) x *&＃61; 10, x &＃43;&＃61; (c - &＃39;0&＃39;),c &＃61; getchar();n &＃61; x*tmp;return true;
}
template <class T>
inline void write(T n)
{if(n <0){putchar(&＃39;-&＃39;);n &＃61; -n;}int len &＃61; 0,data[20];while(n){data[len&＃43;&＃43;] &＃61; n%10;n /&＃61; 10;}if(!len) data[len&＃43;&＃43;] &＃61; 0;while(len--) putchar(data[len]&＃43;48);
}
//-----------------------------------const int MAXN&＃61;1010;
const int MOD&＃61;1e9&＃43;7;ll dp[MAXN][MAXN];
int n,K;struct Edge
{int to,next;
}e[MAXN<<1];
int head[MAXN],tot;void init()
{CLR(dp,0);CLR(head,-1);tot&＃61;0;
}void addedge(int u,int v)
{e[tot].to&＃61;v;e[tot].next&＃61;head[u];head[u]&＃61;tot&＃43;&＃43;;
}ll fac[MAXN],inv[MAXN];
int sz[MAXN];void dfs(int u,int fa&＃61;-1)
{sz[u]&＃61;1;for(int i&＃61;head[u];~i;i&＃61;e[i].next)if(e[i].to!&＃61;fa){dfs(e[i].to,u);sz[u]&＃43;&＃61;sz[e[i].to];}
}int main()
{inv[0]&＃61;inv[1]&＃61;1;fac[0]&＃61;fac[1]&＃61;1;for(int i&＃61;2; i1]*i%MOD;}int T,cas&＃61;1;read(T);while(T--){init();read(n),read(K);for(int i&＃61;0,u,v;i1;i&＃43;&＃43;){read(u),read(v);addedge(u,v);addedge(v,u);}dfs(1);dp[0][0]&＃61;1;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)for(int j&＃61;0;j<&＃61;K;j&＃43;&＃43;){dp[i][j]&＃61;dp[i-1][j]*(sz[i]-1)%MOD*inv[sz[i]]%MOD;if(j>0)dp[i][j]&＃61;(dp[i][j]&＃43;dp[i-1][j-1]*inv[sz[i]]%MOD)%MOD;}ll ans&＃61;dp[n][K]*fac[n]%MOD;printf("Case #%d: %I64d\n",cas&＃43;&＃43;, ans);}return 0;
}