LOJ 2546 「JSOI2018」潜入行动—

题目：https://loj.ac/problem/2546

dp[ i ][ j ][ 0/1 ][ 0/1 ] 表示 i 子树，用 j 个点，是否用 i ， i 是否被覆盖。

注意 s1<=s0 ，别弄出负角标。

用 if 判断一下，如果有值再转移，会快非常多。

复杂度是 O(n*k) 的。证明：https://www.cnblogs.com/cjyyb/p/10416839.html

先约定如果一个小于 k 的子树和一个大于 k 的子树合并，在小于 k 的子树那里看复杂度。

1.两个小于 k 的子树 cr 和 v 合并，且合并完之后还是小于 k 的；

　　对于 cr 里的每个点，要和 v 的每个点产生贡献。虽然和很多 v 都这样做了，但这些 v 的大小加起来小于 k （因为规定合并完还是小于 k ），所以一个点贡献 O(k) 次。

　　如果合并完大于 k ，就在 “一个小于 k 的子树和一个大于 k 的子树合并” 的部分考虑复杂度了。

2.一个小于 k 的子树 cr 和一个大于 k 的子树 v 合并。

　　对于 cr 里的每个点，此时都要进行 O(k) 次贡献。合并完之后 cr 的大小变成大于 k ，所以这种贡献，每个点只会经历一次。

3.一个大于 k 的子树 cr 和一个大于 k 的子树 v 合并。

　　产生 k² 的贡献。如果是两个大小为 k 的子树，合并之后大小变成 2*k ；再合并进来一个大小为 k 的，大小就变成 3*k ；即这种合并最多 \( \frac{n}{k} \) 次。

综上，复杂度是 O(n*k) 的。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

int Mx(int a,int b){return a>b?a:b;}

int Mn(int a,int b){return a<b?a:b;}

const int N=1e5+,M=,mod=1e9+;

int upt(int x){while(x>=mod)x-=mod;while(x<)x+=mod;return x;}

int n,k,hd[N],xnt,to[N<<],nxt[N<<];

int siz[N],dp[N][M][][],tp[][];

void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}

void cz(int &x,int y){x=upt(x+y);}

void dfs(int cr,int fa)

{

  dp[cr][][][]=dp[cr][][][]=; siz[cr]=;

  for(int i=hd[cr],v;i;i=nxt[i])

    if((v=to[i])!=fa)

      {

    dfs(v,cr);

    for(int s0=Mn(k,siz[cr]+siz[v]);s0>=;s0--)

      {

        tp[][]=tp[][]=tp[][]=tp[][]=;

        for(int s1=Mx(,s0-siz[cr]),lm=Mn(s0,Mn(siz[v],k));s1<=lm;s1++)

          {

        int d=s0-s1;

        if(dp[cr][d][][])

          {

            cz(tp[][],(ll)dp[cr][d][][]*dp[v][s1][][]%mod);

            cz(tp[][],(ll)dp[cr][d][][]*dp[v][s1][][]%mod);

          }

        if(dp[cr][d][][])

          cz(tp[][],(ll)dp[cr][d][][]*(dp[v][s1][][]+dp[v][s1][][])%mod);

        if(dp[cr][d][][])

          {

            cz(tp[][],(ll)dp[cr][d][][]*(dp[v][s1][][]+dp[v][s1][][])%mod);

            cz(tp[][],(ll)dp[cr][d][][]*(dp[v][s1][][]+dp[v][s1][][])%mod);

          }

        if(dp[cr][d][][])

          {

            cz(tp[][],(ll)dp[cr][d][][]

               *((ll)dp[v][s1][][]+dp[v][s1][][]+dp[v][s1][][]+dp[v][s1][][])%mod);

          }

          }

        for(int f0=;f0<=;f0++)

          for(int f1=;f1<=;f1++)

        dp[cr][s0][f0][f1]=tp[f0][f1];

      }

    siz[cr]+=siz[v];

      }

}

int main()

{

  n=rdn();k=rdn();

  for(int i=,u,v;i<n;i++)

    u=rdn(),v=rdn(),add(u,v),add(v,u);

  dfs(,);

  printf("%d\n",upt(dp[][k][][]+dp[][k][][]));

  return ;

}

巴特西

LOJ 2546 「JSOI2018」潜入行动——树形DP

最新文章

热门文章