Qiuly

「JSOI2018」潜入行动 树形DP loj2546
设 $f_{u,w,0/1,0/1}$ 表示 $u$ 的子树中有 $w$ 个监听器,$u$ 是否($1/0$)安装...
扫描右侧二维码阅读全文
30
2019/05

「JSOI2018」潜入行动 树形DP loj2546

设 $f_{u,w,0/1,0/1}$ 表示 $u$ 的子树中有 $w$ 个监听器,$u$ 是否($1/0$)安装监听器、$u$ 是否($1/0$)被监听的情况下的方案数,最终答案为 $f_{1,k,0,1}+f_{1,k,1,1}$ 。

转移的时候枚举子树,然后合并。具体方案如下(一定满足 $i+j=w$ ):

$f_{u,w,0,0}$ 的转移

首先,我们的子树一定是要被监听到的,不然合并什么啊。而且,子树一定不能放监听器,不然就不满足当前状态了。

这样子就很好办了:

$$ f_{u,w,0,0}=f_{v,i,0,1}\times f_{u,j,0,0} $$

$f_{u,w,0,1}$ 的转移

考虑一下 $u$ 是被之前的儿子监听的还是被当前儿子监听的,如果是之前的儿子监听了 $u$ ,那么当前儿子可以安装也可以不安装监听器(不过当前儿子必须被监听,因为 $u$ 不会监听该儿子) :

$$ f_{u,w,0,1}=(f_{v,i,0,1}+f_{v,i,1,1})\times f_{u,j,0,1} $$

第二种情况就是,$u$ 是被当前儿子监听的,这意味着当前儿子一定安装了监听器,也就是说后两维状态为 $1,1$ :

$$ f_{u,w,0,1}=f_{v,i,1,1}\times f_{u,j,0,0} $$

$f_{u,w,1,0}$ 的转移

这样的情况下,当前儿子可以不被监听(因为可以被父节点 $u$ 监听了) ,不过当前儿子不能安装监听器:

$$ f_{u,w,1,0}=(f_{v,i,0,0}+f_{v,i,0,1})\times f_{u,j,1,0} $$

$f_{u,w,1,1}$ 的转移

同样考虑监听了 $u$ 的是之前的儿子还是当前儿子 $v$ 。如果是之前的儿子监听了 $u$ ,那么 $v$ 可以监听也可以不监听 $u$ ,同样 $v$ 可以安装也可以不安装监听器,因为 $v$ 已经被 $u$ 监听了:

$$ f_{u,w,1,1}=(f_{v,i,0,0}+f_{v,i,0,1}+f_{v,i,1,0}+f_{v,i,1,1})\times f_{u,j,1,1} $$

然后就是 $u$ 是被 $v$ 监听的情况:

$$ f_{u,w,1,1}=(f_{v,i,1,0}+f_{v,i,1,1})\times f_{u,x,1,0} $$

时间复杂度 $O(nk)$ ,过得去。其实实际实现中还可以优化一点,就是记录一个 $sz$ ,然后枚举状态的时候和 $k$ 取 $\min$ 。不过 $k$ 不大,这样做估计也快不了多少。

上面的四个情况貌似可以将后两维压成一维,听说高维数组很慢(迷信.jpg)

Code:

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1e5+1;
const int K=1e2+1;
#define p 1000000007

int f[N][K][4],g[K][4];
int n,m,sz[N],cnt,head[N];
struct Edge{int nxt,to,val;}G[N<<1];

void add(int u,int v) {
    G[++cnt]=(Edge){head[u],v},head[u]=cnt;
    G[++cnt]=(Edge){head[v],u},head[v]=cnt;
}

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

inline void inc(int&x,int y) {x+=y;if(x>=p)x-=p;}
inline int pls(int x,int y) {x+=y;if(x>=p)x-=p;return x;}
void dfs(int u,int fa) {
    sz[u]=1;
    f[u][0][0]=f[u][1][2]=1;
    for(int e=head[u],v;e;e=G[e].nxt)if((v=G[e].to)!=fa) {
        dfs(v,u);
        memcpy(g,f[u],sizeof(g)),memset(f[u],0,sizeof(f[u]));
        for(int i=0;i<=min(sz[v],m);++i) {
            int sum=pls(pls(f[v][i][0],f[v][i][1]),pls(f[v][i][2],f[v][i][3]));
            int val1=pls(f[v][i][1],f[v][i][3]);
            int val2=pls(f[v][i][0],f[v][i][1]);
            int val3=pls(f[v][i][2],f[v][i][3]);
            for(int j=0;j<=min(sz[u],m)&&i+j<=m;++j) {
                int k=i+j;
                inc(f[u][k][0],(ll)f[v][i][1]*g[j][0]%p);
                inc(f[u][k][1],(ll)val1*g[j][1]%p);
                inc(f[u][k][1],(ll)f[v][i][3]*g[j][0]%p);
                inc(f[u][k][2],(ll)val2*g[j][2]%p);
                inc(f[u][k][3],(ll)sum*g[j][3]%p);
                inc(f[u][k][3],(ll)val3*g[j][2]%p);
            }
        }sz[u]+=sz[v];
    }
}

int main() {
    IN(n),IN(m);
    for(int i=1,u,v;i<n;++i) IN(u),IN(v),add(u,v);
    dfs(1,0);
    int ans=pls(f[1][m][1],f[1][m][3]);
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 05 月 30 日 03 : 26 PM

发表评论