BZOJ5314：[JSOI2018]潜入行动—

BZOJ5314：[JSOI2018]潜入行动——题解

外星人又双叒叕要攻打地球了，外星母舰已经向地球航行！这一次，JYY已经联系好了黄金舰队，打算联合所有JSOIer抵御外星人的进攻。在黄金舰队就位之前，JYY打算事先了解外星人的进攻计划。现在，携带了监听设备的特工已经秘密潜入了外星人的母舰，准备对外星人的通信实施监听。外星人的母舰可以看成是一棵n个节点、n-1条边的无向树，树上的节点用1,2...n编号。JYY的特工已经装备了隐形模块，可以在外星人母舰中不受限制地活动，可以神不知鬼不觉地在节点上安装监听设备。如果在节点u安装监听设备，则JYY能够监听与u直接相邻所有的节点的通信。换言之，如果在节点u安装监听设备，则对于树中每一条边(u,v)，节点v都会被监听。特别注意放置在节点u的监听设备并不监听u本身的通信，这是JYY特别为了防止外星人察觉部署的战术。

JYY的特工一共携带了k个监听设备，现在JYY想知道，有多少种不同的放置监听设备的方法，能够使得母舰上所有节点的通信都被监听？为了避免浪费，每个节点至多只能安装一个监听设备，且监听设备必须被用完。

一个很好想的dp[i][j][0/1][0/1]表示i为根的子树放了j个设备，i结点没放/放了设备，i结点没被控制/控制。

然后就是惊天地泣鬼神的转移了，看代码应该能看懂吧，我们其实就是把每棵子树按照乘法原理依次加入即可。

难还真不难，但是dp式子真心长，还卡你常，你就没话说了（虽然最坏复杂度是O(nkk)的但是显然达不到，而且这种树形dp依赖每棵子树更新的话应该是有O(nk)做法的。）

UPD：听说这个复杂度就是O(nk)的？然而网上的证明并没有看懂……

#include<cmath>
#include<queue>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int p=1e9+7;
const int N=1e5+5;
const int K=105;
inline int read(){
    int X=0,w=0;char ch=0;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
struct node{
    int to,nxt;
}e[N*2];
int n,k,cnt,head[N],size[N];
int f[N][K][2][2],g[K][2][2];
inline void ins(int u,int v){
    e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
}
inline void add(int &x,ll y){
    x+=y%p;
    if(x>=p)x-=p;
}
void dfs(int u,int fa){
    size[u]=1;
    f[u][0][0][0]=f[u][1][1][0]=1;
    for(int i=head[u];i;i=e[i].nxt){
    int v=e[i].to;
    if(v==fa)continue;
    dfs(v,u);
    for(int i=0,l1=min(k,size[u]);i<=l1;i++){
        g[i][0][0]=f[u][i][0][0];f[u][i][0][0]=0;
        g[i][0][1]=f[u][i][0][1];f[u][i][0][1]=0;
        g[i][1][0]=f[u][i][1][0];f[u][i][1][0]=0;
        g[i][1][1]=f[u][i][1][1];f[u][i][1][1]=0;
    }
    for(int i=0,l1=min(k,size[u]);i<=l1;i++){
        for(int j=0,l2=min(k-i,size[v]);j<=l2;j++){
        add(f[u][i+j][0][0],(ll)g[i][0][0]*f[v][j][0][1]);
        add(f[u][i+j][0][1],(ll)g[i][0][1]*(f[v][j][0][1]+f[v][j][1][1])+(ll)g[i][0][0]*f[v][j][1][1]);
        add(f[u][i+j][1][0],(ll)g[i][1][0]*(f[v][j][0][0]+f[v][j][0][1]));
        add(f[u][i+j][1][1],(ll)g[i][1][1]*((ll)f[v][j][0][0]+f[v][j][0][1]+f[v][j][1][0]+f[v][j][1][1])+(ll)g[i][1][0]*(f[v][j][1][0]+f[v][j][1][1]));
        }
    }
    size[u]+=size[v];
    }
}
int main(){
    n=read(),k=read();
    for(int i=1;i<n;i++){
    int u=read(),v=read();
    ins(u,v);ins(v,u);
    }
    dfs(1,0);
    printf("%d
",(f[1][k][0][1]+f[1][k][1][1])%p);
    return 0;
}