首页 > 其他分享 >111

111

时间:2024-12-18 20:45:50浏览次数:8  
标签:int define Add 111 mod getchar

#include <bits/stdc++.h>
#define re register
#define int long long
#define Add(a,b) (((a) + (b)) % mod)
#define Mul(a,b) ((a) * (b) % mod)
#define chAdd(a,b) (a = Add(a,b))

using namespace std;

const int N = 110,M = N * 2;
const int mod = 1e9 + 7;
int n,k,ans;
int tmp[N],dp[N][N];
int idx,h[N],ne[M],e[M];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

inline void add(int a,int b){
    ne[idx] = h[a];
    e[idx] = b;
    h[a] = idx++;
}

inline void dfs(int u,int fa){
    dp[u][0] = 1; dp[u][k + 1] = 1;
    for (re int i = h[u];~i;i = ne[i]){
        int v = e[i];
        if (v == fa) continue;
        dfs(v,u);
        memset(tmp,0,sizeof(tmp));
        for (re int i = 0;i <= 2 * k;i++){
            for (re int j = 0;j <= 2 * k;j++){
                if (i + j <= 2 * k) chAdd(tmp[min(i,j + 1)],Mul(dp[u][i],dp[v][j]));
                else chAdd(tmp[max(i,j + 1)],Mul(dp[u][i],dp[v][j]));
            }
        }
        for (re int i = 0;i <= 2 * k;i++) dp[u][i] = tmp[i];
    }
}

signed main(){
    memset(h,-1,sizeof(h));
    n = read(),k = read();
    for (re int i = 1,a,b;i < n;i++){
        a = read(),b = read();
        add(a,b); add(b,a);
    }
    dfs(1,0);
    for (re int i = 0;i <= k;i++) chAdd(ans,dp[1][i]);
    printf("%lld",ans);
    return 0;
}

标签:int,define,Add,111,mod,getchar
From: https://www.cnblogs.com/WaterSun/p/18615791

相关文章