潜入行动「JSOI2018」

题意

给定一颗无根树，可以在上面放置恰好\(k\)个监听器，与监听器相连的节点被监听，但监听器本身不会被监听。

要求监听所有节点，求方案数模1e9+7。

思路

状态略有毒瘤之处的树上dp。

子状态为\(dp[n][k][0/1][0/1]\)表示在以\(n\)为根的子树中选择了\(k\)个节点，其中是否选择\(n\)，\(n\)是否被监听。

状态转移方程显然，就是极其容易写错。

本题卡\(long long\)，注意使用\(unsigned int\)

代码

#include <bits/stdc++.h>

using namespace std;

namespace StandardIO {

    streambuf*in=cin.rdbuf();
    char bb[1000000],*s=bb,*t=bb;
    #define gc() (s==t&&(t=(s=bb)+in->sgetn(bb,1000000),s==t)?EOF:*s++)
    template<typename T> inline void read(T &x){
        x=0;
        char ch=gc();
        while(ch<48)ch=gc();
        while(ch>=48)x=x*10+ch-48,ch=gc();
    }
    template<typename T> inline void write (T x) {
        if (x<0) putchar('-'),x=-x;
        if (x>=10) write(x/10);
        putchar(x%10+'0');
    }

}

using namespace StandardIO;

namespace Solve {
    
    const int N=100001;
    const int MOD=1000000007;
    
    int n,k,ans;
    int cnt;
    int head[N];
    struct node {
        int to,next;
    } edge[N<<1];
    unsigned int dp[N][101][2][2];
    long long cur[101][2][2],size[N];

    inline int min (const int &x,const int &y) {
        return (x>y)?y:x;
    }
    inline int max (const int &x,const int &y) {
        return (x<y)?y:x;
    }
    inline void add (int a,int b) {
        edge[++cnt].to=b,edge[cnt].next=head[a],head[a]=cnt;
    }
    void dfs (int now,int fa) {
        size[now]=1,dp[now][0][0][0]=dp[now][1][1][0]=1;
        for (register int i=head[now]; i; i=edge[i].next) {
            int to=edge[i].to;
            if (to==fa) continue;
            dfs(to,now);
            int limit1=min(k,size[now]),limit2=min(k,size[to]);
            for (register int j=0; j<=limit1; ++j) {
                cur[j][0][0]=dp[now][j][0][0],cur[j][0][1]=dp[now][j][0][1];
                cur[j][1][0]=dp[now][j][1][0],cur[j][1][1]=dp[now][j][1][1];
                dp[now][j][0][0]=dp[now][j][0][1]=dp[now][j][1][0]=dp[now][j][1][1]=0;
            }
            for (register int j=0; j<=limit1; ++j) {
                for (register int t=0; t<=limit2&&j+t<=k; ++t) {
                    dp[now][j+t][0][0]+=cur[j][0][0]*dp[to][t][0][1]%MOD;
                    dp[now][j+t][0][1]+=(cur[j][0][0]*dp[to][t][1][1]%MOD+cur[j][0][1]*(dp[to][t][0][1]+dp[to][t][1][1])%MOD)%MOD;
                    dp[now][j+t][1][0]+=cur[j][1][0]*((dp[to][t][0][0]+dp[to][t][0][1])%MOD)%MOD;
                    dp[now][j+t][1][1]+=(cur[j][1][0]*(dp[to][t][1][0]+dp[to][t][1][1])%MOD+cur[j][1][1]*(dp[to][t][0][0]+dp[to][t][1][0]+dp[to][t][0][1]+dp[to][t][1][1])%MOD)%MOD;
                    dp[now][j+t][0][0]%=MOD,dp[now][j+t][0][1]%=MOD;
                    dp[now][j+t][1][0]%=MOD,dp[now][j+t][1][1]%=MOD;
                }
            }
            size[now]+=size[to];
        }
    }
    
    inline void MAIN () {
        read(n),read(k);
        for (register int i=1; i<n; ++i) {
            int u,v;
            read(u),read(v);
            add(u,v),add(v,u);
        }
        dfs(1,1);
        ans=(dp[1][k][0][1]+dp[1][k][1][1])%MOD;
        write(ans);
    }
    
}

int main () {
    Solve::MAIN();
}

潜入行动「JSOI2018」

原文：https://www.cnblogs.com/ilverene/p/11382271.html