潜入行动 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;}小结：这种题其实只要做过一道就行了。
[bzoj5314][Jsoi2018]潜入行动_树形背包dp
原文地址：https://www.cnblogs.com/ShuraK/p/10163715.html