[bzoj5314][Jsoi2018]潜入行动_树形背包dp

潜入行动 bzoj-5314 Jsoi-2018

题目大意：题目链接。

注释：略。

---

想法：

学长给我们除了一套考试题，三个学长一人一道这是T1.

好吧好吧，傻逼背包......

复杂度$O(nk)$。

Code：

#include<bits/stdc++.h>

#define mod 1000000007

#define N 100010

using namespace std; typedef long long ll;

int n,K,size[N];

ll g[101][2][2]; int f[N][101][2][2];

int tot,head[N],nxt[N<<1],to[N<<1];

inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}

int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}

inline void OrzWinniechen(int &x,ll y) {x+y>=mod?x+=y-mod:x+=y;}

inline void add(int x,int y) {to[++tot]=y; nxt[tot]=head[x]; head[x]=tot;}

void dfs(int pos,int fa)

{

    size[pos]=1; f[pos][0][0][0]=f[pos][1][1][0]=1;

    for(int o=head[pos];o;o=nxt[o]) if(to[o]!=fa)

    {

        int v=to[o]; dfs(v,pos);

        int kkk=min(size[pos],K),suika=min(size[v],K);

        for(int i=0,r=kkk;i<=r;i++)

        {

            g[i][0][0]=f[pos][i][0][0],f[pos][i][0][0]=0;

            g[i][0][1]=f[pos][i][0][1],f[pos][i][0][1]=0;

            g[i][1][0]=f[pos][i][1][0],f[pos][i][1][0]=0;

            g[i][1][1]=f[pos][i][1][1],f[pos][i][1][1]=0;

        }

        for(int i=0,r1=kkk;i<=r1;i++)

            for(int j=0,r2=suika;i+j<=K&&j<=r2;j++)

            {

				// puts("OrzWinniechen");

                OrzWinniechen(f[pos][i+j][0][0],

                g[i][0][0]*f[v][j][0][1]%mod);

				// printf("Shit %lld\n",f[pos][i+j][0][0]);

                OrzWinniechen(f[pos][i+j][0][1],

                (g[i][0][0]*f[v][j][1][1]

                +g[i][0][1]*(f[v][j][0][1]

                +f[v][j][1][1]))%mod);

				// printf("Shit %lld\n",f[pos][i+j][0][1]);

                OrzWinniechen(f[pos][i+j][1][0],

                g[i][1][0]*(f[v][j][0][0]+f[v][j][0][1])%mod);

				// printf("Shit %lld\n",f[pos][i+j][1][0]);

                OrzWinniechen(f[pos][i+j][1][1],

                (g[i][1][0]*(f[v][j][1][0]+f[v][j][1][1])

                +g[i][1][1]*(f[v][j][0][0]+f[v][j][1][0])

                +g[i][1][1]*(f[v][j][0][1]+f[v][j][1][1]))%mod);

				// printf("Shit %lld\n",f[pos][i+j][1][1]);

            }

        size[pos]+=size[to[o]];

    }

}

int main()

{

    // freopen("polynomial.in","r",stdin);

    // freopen("polynomial.out","w",stdout);

    n=rd(),K=rd(); for(int i=1;i<n;i++) {int x=rd(),y=rd(); add(x,y); add(y,x);}

    dfs(1,1);

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

    return 0;

}

小结：这种题其实只要做过一道就行了。