CF735E Ostap and Tree

比较毒瘤的树形DP，子状态难想。这是主要是搬运一篇题解。

用\(f[i][j]\)表示\(i\)的子树中离\(i\)最近黑点的距离为\(j\)，且距离超过\(j\)的点都被满足的方案数。转移时新建一个临时数组\(tmp\)保存转移后的\(f[x]\)。设\(y\)是\(x\)的子结点，枚举\(f[x][i]\)和\(f[y][j]\)，转移如下：

若\(i+j≤2k\)，则此时\(min(i,j+1)≤k\)，对于长度为\(i+j+1\)的链上的所有点都可以找到一边距离\(≤k\)，因此状态合并以后是合法状态，转移\(tmp[min(i,j+1)]+=f[x][i]×f[y][j]\)；
若\(i+j>2k\)，则此时\(max(i,j+1)>k\)，链上肯定会存在一些点两边都够不到，转移\(tmp[max(i,j+1)]+=f[x][i]×f[y][j]\)。

初始状态\(f[x][0]=1\)，表示不考虑子树内的情况，选择自己的方案数为\(1\)；\(f[x][k+1]=1\)，表示自己本身不满足，但子结点都被满足的情况，主要是方便转移。

答案为\(∑i<=kf[root][i]\)。

时间复杂度\(O(nk2)\)。

代码如下

#include<cstdio>

#include<cctype>

#include<algorithm>

#include<forward_list>

typedef long long int64;

inline int getint() {

    register char ch;

    while(!isdigit(ch=getchar()));

    register int x=ch^'0';

    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

    return x;

}

const int N=101,K=41,mod=1e9+7;

int k,f[N][K],tmp[K];

std::forward_list<int> e[N];

inline void add_edge(const int &u,const int &v) {

    e[u].push_front(v);

    e[v].push_front(u);

}

void dfs(const int &x,const int &par) {

    f[x][0]=f[x][k+1]=1;

    for(int &y:e[x]) {

        if(y==par) continue;

        dfs(y,x);

        std::fill(&tmp[0],&tmp[k*2]+1,0);

        for(register int i=0;i<=k*2;i++) {

            for(register int j=0;j<=k*2;j++) {

                (tmp[i+j<=k*2?std::min(i,j+1):std::max(i,j+1)]+=(int64)f[x][i]*f[y][j]%mod)%=mod;

            }

        }

        std::copy(&tmp[0],&tmp[k*2]+1,f[x]);

    }

}

int main() {

    const int n=getint();k=getint();

    for(register int i=1;i<n;i++) {

        add_edge(getint(),getint());

    }

    dfs(1,0);

    int ans=0;

    for(register int i=0;i<=k;i++) {

        (ans+=f[1][i])%=mod;

    }

    printf("%d\n",ans);

    return 0;

}

巴特西

CF735E Ostap and Tree

最新文章

热门文章