[洛谷 4516,loj 2546][JSOI2018]潜入行动

题目链接

https://www.luogu.org/problem/P4516

https://loj.ac/problem/2546

题解

题目给出的树是一棵无根树，为了方便起见，我们指定 \(1\) 点作为整棵树的根节点。

设 \(f(i,j,0/1,0/1)\) 表示以 \(i\) 为根节点的子树在全部被监控的前提下，安装了 \(j\) 个装置，当前节点是否安装装置，当前节点是否被监控的情况下对应的方案数。

转移时对于每个节点，枚举子节点，考虑以下几种情况：

1. 当前节点没有安装装置，也没有被监控：这时子节点不能安装装置；
2. 当前节点没有安装装置，但被监控：分两种情况，若当前节点被其他节点监控，这时候子节点是否安装装置不重要了；否则子节点需要安装装置监控当前节点；
3. 当前节点安装装置，但不被监控：子节点是否被监控无所谓；
4. 当前节点安装装置，也被监控：若当前节点被其他节点监控，子节点的状态是任意的；否则需要在子节点安装装置来监控当前节点。

转移方程太长了，就不详细写出了。

还有一点要注意的是，因为内存限制较紧张，数组不能定义为 long long 类型，因此要小心变量溢出的问题。

#include <cstdio>
#include <algorithm>
#define MOD 1000000007
using namespace std;
struct edge
{
 int v,next;
}e[200005];
int f[100005][105][2][2],g[105][2][2],siz[100005],head[100005],cnt,n,k;
void addedge(int u,int v)
{
 e[++cnt].v=v;
 e[cnt].next=head[u];
 head[u]=cnt;
}
void dfs(int u,int fa)
{
 siz[u]=1,f[u][0][0][0]=f[u][1][1][0]=1;
 for(int i=head[u];i;i=e[i].next)
  if(e[i].v!=fa)
  {
   int v=e[i].v;
   dfs(v,u);
   for(int j=0;j<=min(siz[u],k);j++)
   {
    g[j][0][0]=f[u][j][0][0],f[u][j][0][0]=0;
    g[j][0][1]=f[u][j][0][1],f[u][j][0][1]=0;
    g[j][1][0]=f[u][j][1][0],f[u][j][1][0]=0;
    g[j][1][1]=f[u][j][1][1],f[u][j][1][1]=0;
   }
   for(int i=0;i<=min(k,siz[u]);i++)
    for(int j=0;j<=min(k-i,siz[v]);j++)
    {
     f[u][i+j][0][0]=(f[u][i+j][0][0]+(long long)g[i][0][0]*f[v][j][0][1])%MOD;
     f[u][i+j][0][1]=(f[u][i+j][0][1]+(long long)g[i][0][1]*(f[v][j][1][1]+f[v][j][0][1])%MOD
                     +(long long)g[i][0][0]*f[v][j][1][1])%MOD;
     f[u][i+j][1][0]=(f[u][i+j][1][0]+(long long)g[i][1][0]*(f[v][j][0][0]+f[v][j][0][1]))%MOD;
     f[u][i+j][1][1]=(f[u][i+j][1][1]+(long long)g[i][1][0]*(f[v][j][1][0]+f[v][j][1][1])%MOD
                     +(long long)g[i][1][1]*((long long)f[v][j][0][1]+f[v][j][1][1]+f[v][j][0][0]+f[v][j][1][0]))%MOD;
    }
   siz[u]+=siz[v];
  }
}
int main()
{
 scanf("%d%d",&n,&k);
 for(int i=1;i<n;i++)
 {
  int u,v;
  scanf("%d%d",&u,&v);
  addedge(u,v);
  addedge(v,u);
 }
 dfs(1,0);
 printf("%d\n",(f[1][k][0][1]+f[1][k][1][1])%MOD);
 return 0;
}