HDU 5378 Leader in Tree Land【树形DP】

女爷i 2022-08-03 16:44 1阅读 0赞

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

// whn6325689
    // Mr.Phoebe
    // http://blog.csdn.net/u013007900
    #include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstring>
    #include <climits>
    #include <complex>
    #include <fstream>
    #include <cassert>
    #include <cstdio>
    #include <bitset>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <ctime>
    #include <set>
    #include <map>
    #include <cmath>
    #include <functional>
    #include <numeric>
    #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<ll, ll> pll;
    typedef complex<ld> point;
    typedef pair<int, int> pii;
    typedef pair<pii, int> 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+((y-x)>>1))
    #define ls (idx<<1)
    #define rs (idx<<1|1)
    #define lson ls,l,mid
    #define rson rs,mid+1,r
    #define root 1,1,n
    
    template<class T>
    inline bool read(T &n)
    {
        T x = 0, tmp = 1;
        char c = getchar();
        while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
        if(c == EOF) return false;
        if(c == '-') c = getchar(), tmp = -1;
        while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
        n = x*tmp;
        return true;
    }
    template <class T>
    inline void write(T n)
    {
        if(n < 0)
        {
            putchar('-');
            n = -n;
        }
        int len = 0,data[20];
        while(n)
        {
            data[len++] = n%10;
            n /= 10;
        }
        if(!len) data[len++] = 0;
        while(len--) putchar(data[len]+48);
    }
    //-----------------------------------
    
    const int MAXN=1010;
    const int MOD=1e9+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=0;
    }
    
    void addedge(int u,int v)
    {
        e[tot].to=v;
        e[tot].next=head[u];
        head[u]=tot++;
    }
    void dfs(int u,int fa=-1)
    {
        sz[u]=1;
        for(int i=head[u]; ~i; i=e[i].next)
        {
            int v=e[i].to;
            if(v==fa)   continue;
            dfs(v,u);
            sz[u]+=sz[v];
        }
        ret[0][0]=1;
        int all=0,cur=0;
        for(int i=head[u]; ~i; i=e[i].next)
        {
            int v=e[i].to;
            if(v==fa)   continue;
            for(int j=0; j<=min(K,all+sz[v]+1); j++)ret[cur^1][j]=0;
            for(int j=min(K,all); j>=0; j--)
            {
                if(!ret[cur][j])    continue;
                for(int k=1; k<=min(K,sz[v]); k++)
                {
                    ret[cur^1][j+k]+=ret[cur][j]*dp[v][k]%MOD*C[sz[u]-1-all][sz[v]]%MOD;
                    ret[cur^1][j+k]%=MOD;
                }
            }
            cur^=1;
            all+=sz[v];
        }
        for(int i=min(K,sz[u]); i>=1; i--)
        {
            // printf("dp[%d][%d]=%I64d\n",v,i,ret[cur][i]);
            dp[u][i]=ret[cur][i]*(sz[u]-1)%MOD+ret[cur][i-1];
            dp[u][i]%=MOD;
        }
    }
    int main()
    {
        C[0][0]=1;
        for(int i=1; i<MAXN; i++)
        {
            C[i][0]=C[i][i]=1;
            for(int j=1; j<i; j++)
                C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
        }
        int T,cas=1;
        read(T);
        while(T--)
        {
            init();
            read(n),read(K);
            for(int i=0, u, v; i<n-1; i++)
            {
                read(u),read(v);
                addedge(u,v);
                addedge(v,u);
            }
            dfs(1);
            printf("Case #%d: %I64d\n",cas++,dp[1][K]);
        }
        return 0;
    }

可以用求概率的思想来解决这个问题。令以i号节点为根的子树为第i棵子树，设这颗子树恰好有sz\[i\]个点。那么第i个点是第i棵子树最大值的概率为1/sz\[i\]，不是最大值的概率为(sz\[i\]−1)/sz\[i\]。现在可以求解恰好有k个最大值的概率。  
令dp\[i\]\[j\]表示考虑编号从1到i的点，其中恰好有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 <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstring>
    #include <climits>
    #include <complex>
    #include <fstream>
    #include <cassert>
    #include <cstdio>
    #include <bitset>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <ctime>
    #include <set>
    #include <map>
    #include <cmath>
    #include <functional>
    #include <numeric>
    #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<ll, ll> pll;
    typedef complex<ld> point;
    typedef pair<int, int> pii;
    typedef pair<pii, int> 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+((y-x)>>1))
    #define ls (idx<<1)
    #define rs (idx<<1|1)
    #define lson ls,l,mid
    #define rson rs,mid+1,r
    #define root 1,1,n
    
    template<class T>
    inline bool read(T &n)
    {
        T x = 0, tmp = 1;
        char c = getchar();
        while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
        if(c == EOF) return false;
        if(c == '-') c = getchar(), tmp = -1;
        while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
        n = x*tmp;
        return true;
    }
    template <class T>
    inline void write(T n)
    {
        if(n < 0)
        {
            putchar('-');
            n = -n;
        }
        int len = 0,data[20];
        while(n)
        {
            data[len++] = n%10;
            n /= 10;
        }
        if(!len) data[len++] = 0;
        while(len--) putchar(data[len]+48);
    }
    //-----------------------------------
    
    const int MAXN=1010;
    const int MOD=1e9+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=0;
    }
    
    void addedge(int u,int v)
    {
        e[tot].to=v;
        e[tot].next=head[u];
        head[u]=tot++;
    }
    
    ll fac[MAXN],inv[MAXN];
    int sz[MAXN];
    
    void dfs(int u,int fa=-1)
    {
        sz[u]=1;
        for(int i=head[u];~i;i=e[i].next)
            if(e[i].to!=fa)
            {
                dfs(e[i].to,u);
                sz[u]+=sz[e[i].to];
            }
    }
    
    int main()
    {
        inv[0]=inv[1]=1;
        fac[0]=fac[1]=1;
        for(int i=2; i<MAXN; i++)
        {
            inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
            fac[i]=fac[i-1]*i%MOD;
        }
        int T,cas=1;
        read(T);
        while(T--)
        {
            init();
            read(n),read(K);
            for(int i=0,u,v;i<n-1;i++)
            {
                read(u),read(v);
                addedge(u,v);addedge(v,u);
            }
            dfs(1);
            dp[0][0]=1;
            for(int i=1;i<=n;i++)
                for(int j=0;j<=K;j++)
                {
                    dp[i][j]=dp[i-1][j]*(sz[i]-1)%MOD*inv[sz[i]]%MOD;
                    if(j>0)
                        dp[i][j]=(dp[i][j]+dp[i-1][j-1]*inv[sz[i]]%MOD)%MOD;
                }
            ll ans=dp[n][K]*fac[n]%MOD;
            printf("Case #%d: %I64d\n",cas++, ans);
    
        }
        return 0;
    }