题目描述

输入

输出

样例输入

3

2 2 0

1 2

3 3 2

1 3

1 2

3 3 1

1 2

2 3

样例输出

4

2

12

数据范围

样例解释

解法

设f[i][j]为在第i个点填了j的合法方案。

则f[i][j]=∏(f[son(i)][l])(l∈[1,j−k]∪[j+k,m])。

时间复杂度为O(nm)。

观察到f值呈对称状，且中间一段的值是相同的。

利用这个性质优化动态规划。

代码

#include<iostream>

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<algorithm>

#define ll long long

#define ln(x,y) ll(log(x)/log(y))

#define sqr(x) ((x)*(x))

using namespace std;

const char* fin="label.in";

const char* fout="label.out";

const ll inf=0x7fffffff;

const ll maxn=107,maxm=11007,mo=1000000007;

ll t,n,m,delta,i,j,k,tot,ans,tmd;

ll fi[maxn],la[maxn*2],ne[maxn*2];

ll f[maxn][maxm],g[maxn][maxm],h[maxn][maxm];

void add_line(ll a,ll b){

    tot++;

    ne[tot]=fi[a];

    la[tot]=b;

    fi[a]=tot;

}

void dfs(ll v,ll from){

    ll i,j,k,tmp,pre=-1,tmb=0,o;

    for (i=1;i<maxm;i++) f[v][i]=1;

    for (k=fi[v];k;k=ne[k])

        if (la[k]!=from){

            dfs(la[k],v);

            for (i=1;i<=tmd;i++){

                tmp=0;

                if (delta==0){

                    tmp=(tmp+g[la[k]][i]+h[la[k]][i]+mo-f[la[k]][i])%mo;

                }else{

                    j=i-delta;

                    if (j>0) tmp=(tmp+g[la[k]][j])%mo;

                    j=i+delta;

                    if (j<=m) tmp=(tmp+h[la[k]][j])%mo;

                }

                f[v][i]=(f[v][i]*tmp)%mo;

            }

        }

    for (i=2,j=tmd;i<=j;i++) if (f[v][i]==f[v][i-1]) {

        pre=i-2;

        break;

    }else tmb=(tmb+f[v][i-1])%mo;

    if (pre==-1) pre=tmd-1;//,tmb=(tmb+f[v][pre])%mo;

    for (i=1;i<=pre;i++) g[v][i]=(g[v][i-1]+f[v][i])%mo;

    for (j=min(m-pre+1,maxm);i<j;i++) g[v][i]=(g[v][i-1]+f[v][pre+1])%mo;

    for (j=min(m,maxm-1);i<=j;i++) g[v][i]=(g[v][i-1]+f[v][m-i+1])%mo;

    h[v][1]=(tmb*2+(m-2*pre+mo)%mo*f[v][pre+1])%mo;

    for (i=2;i<=pre+1;i++) h[v][i]=(h[v][i-1]-f[v][i-1]+mo)%mo;

    for (j=min(m-pre+1,maxm-1);i<=j && i<=m;i++) h[v][i]=(h[v][i-1]+mo-f[v][pre+1])%mo;

    for (j=min(m,maxm-1);i<=j;i++) h[v][i]=(h[v][i-1]+mo-f[v][m-i+2])%mo;

}

int main(){

    freopen(fin,"r",stdin);

    freopen(fout,"w",stdout);

    scanf("%d",&t);

    for (;t;t--){

        scanf("%d%d%d",&n,&m,&delta);

        tot=0;

        tmd=min((m+1)/2,maxm-delta-5);

        memset(fi,0,sizeof(fi));

        memset(h,0,sizeof(h));

        memset(g,0,sizeof(g));

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

            scanf("%d%d",&j,&k);

            add_line(j,k);

            add_line(k,j);

        }

        dfs(1,0);

        ans=h[1][1];

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

    }

    return 0;

}

启发

观察转移方程的性质，譬如对称之类的，可以优化动态规划。