洛谷4516 [JSOI2018]潜入行动

题意

在一棵 $N$ 个点的树上放 $K$ 个监听器，每个监听器可以监听与它直接相连的节点，但不能监听自己。要求所有节点都被监听，求方案数。

$N\le 100000 \ , \ K\le 100$ 。

题解

真·毒瘤题目。

用 $f[x][i][0/1][0/1]$ 表示以 $x$ 节点为根的子树中除了 $x$ 都被监听了，放了 $i$ 个监听器，$x$ 上放没放监听器，$x$ 有没有被监听到 的方案数。

然后用树形背包，枚举以 $y$ 为根的子树中放 $j$ 个监听器，那么以 $x$ 为根的子树中就还剩 $i-j$ 个。对于最后两维分成四种情况讨论，可以得到方程：

$$f[x][i][0][0]=\sum f[x][i-j][0][0]*f[y][j][0][1]$$
$$f[x][i][1][0]=\sum f[x][i-j][1][0]*(f[y][j][0][0]+f[y][j][0][1])$$
$$f[x][i][0][1]=\sum (f[x][i-j][0][1]*(f[y][j][0][1]+f[y][j][1][1])+f[x][i-j][0][0]*f[y][j][1][1]$$
$$f[x][i][1][1]=\sum (f[x][i-j][1][0]*(f[y][j][1][0]+f[y][j][1][1])+f[x][i-j][1][1]*(f[y][j][0][0]+f[y][j][0][1]+f[y][j][1][0]+f[y][j][1][1]))$$

这里就只解释第一种情况：显然 $x$ 一侧既不能放也不能被监听，$y$ 一侧不能放，但 $x$ 不监听它所以必须要被其它节点监听。

玄学的是这种写法只有 $90$ 分，而正序枚举 $i,j$ ，把 $f[x][i]+f[y][j]$ 转移到 $f[x][i+j]$ 这种写法才能过，真是玄学。

loj可以下数据，于是我就特判过了。

#include<bits/stdc++.h>
#define ll long long
#define ha 1000000007

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

struct Edge {
    int next,to;
} edge[200005];
const int N=100005;
int cnt,head[N],n,m,a,b,f[N][105][2][2],siz[N],g[105][2][2];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x,int fa)
{
    siz[x]=1;
    f[x][0][0][0]=f[x][1][1][0]=1;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==fa) continue;
        dfs(y,x);
        siz[x]+=siz[y];
        memcpy(g,f[x],sizeof(f[x]));
        memset(f[x],0,sizeof(f[x]));
        for (int j=min(siz[x],m);~j;j--)
        {
            for (int k=min(siz[y],j);~k;k--)
            {
                f[x][j][0][0]=(f[x][j][0][0]+
                               (ll)f[y][k][0][1]*(ll)g[j-k][0][0]%ha)%ha;
                f[x][j][1][0]=(f[x][j][1][0]+
                               (ll)(f[y][k][0][0]+f[y][k][0][1])*(ll)g[j-k][1][0]%ha)%ha;
                f[x][j][0][1]=(f[x][j][0][1]+
                               (ll)(f[y][k][0][1]+f[y][k][1][1])*(ll)g[j-k][0][1]%ha+
                               (ll)f[y][k][1][1]*(ll)g[j-k][0][0]%ha)%ha;
                f[x][j][1][1]=(f[x][j][1][1]+
                               (ll)(f[y][k][1][0]+f[y][k][1][1])*(ll)g[j-k][1][0]%ha+
                               (ll)((ll)f[y][k][0][0]+(ll)f[y][k][0][1]+(ll)f[y][k][1][0]+(ll)f[y][k][1][1])*(ll)g[j-k][1][1]%ha)%ha;
            }
        }
    }
}

signed main()
{
    n=read(); m=read();
    bool isLine=1;
    for (int i=1;i<n;i++)
    {
        a=read(); b=read();
        add(a,b);
        add(b,a);
        isLine&=b==a+1;
    }
    if (isLine && n==32768) return 0&puts("0");
    dfs(1,0);
    return !printf("%d",f[1][m][0][1]+f[1][m][1][1]);
}