[JSOI2018]潜入行动 树形DP_复杂计数

code

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <string>

#include <vector>

using namespace std;

void setIO(string a)

{

    freopen((a+".in").c_str(),"r",stdin);

}

#define maxn 100009

#define ll long long

#define mod 1000000007

#define ui unsigned int

int n,K;

vector<int>G[maxn];

ui F[maxn][104][2][2];

int siz[maxn];

ll tmp[maxn][2][2];

void add(ui &a,ll b)

{

    b%=mod;

    ll c=a+b;

    c%=mod;

    a=c;

}

void dfs(int u,int fa)

{

    siz[u]=1;

    F[u][0][0][0]=F[u][1][1][0]=1;

    for(int v=0;v<G[u].size();++v)

    {

        int to=G[u][v];

        if(to==fa) continue;

        dfs(to,u);

        for(int i=0;i<=min(siz[u],K);++i)

        {

            tmp[i][0][0]=F[u][i][0][0],F[u][i][0][0]=0;

            tmp[i][0][1]=F[u][i][0][1],F[u][i][0][1]=0;

            tmp[i][1][0]=F[u][i][1][0],F[u][i][1][0]=0;

            tmp[i][1][1]=F[u][i][1][1],F[u][i][1][1]=0;

        }

        for(int i=0;i<=min(siz[u],K);++i)

            for(int j=0;j<=min(siz[to],K)&&j+i<=K;++j)

            {

                add(F[u][i+j][0][0],(tmp[i][0][0]*F[to][j][0][1])%mod);

                add(F[u][i+j][0][1],(tmp[i][0][0]*F[to][j][1][1]+tmp[i][0][1]*(F[to][j][1][1]+F[to][j][0][1]))%mod);

                add(F[u][i+j][1][0],(tmp[i][1][0]*(F[to][j][0][0]+F[to][j][0][1]))%mod);

                add(F[u][i+j][1][1],(tmp[i][1][0]*(F[to][j][1][1]+F[to][j][1][0]))%mod);

                add(F[u][i+j][1][1],(tmp[i][1][1]*(F[to][j][0][0]+F[to][j][0][1]+F[to][j][1][0]+F[to][j][1][1]))%mod);

            }

        siz[u]+=siz[to];

    }

}

int main()

{

    //setIO("input");

    scanf("%d%d",&n,&K);

    for(int i=1;i<n;++i)

    {

        int a,b;

        scanf("%d%d",&a,&b);

        G[a].push_back(b);

        G[b].push_back(a);

    }

    dfs(1,0);

    printf("%u\n",(F[1][K][0][1]+F[1][K][1][1])%mod);

    return 0;

}

　　

: