求教,为何RE

回复帖子

@卡特琳娜 2018-10-02 11:16 回复

$$RT$$

#include <bits/stdc++.h>
#define newline printf ("\n")
#define space printf (" ")
#define cinfalse ios::sync_with_stdio(false)
#define fread(a) freopen (a".in", "r", stdin), freopen(a".out", "w", stdout)
#define rint register int
#define For(i, a, b) for (rint i = a; i <= b; i ++)
#define Low(i, a, b) for (rint i = a; i >= b; i --)
#define FFr(i, a, b, c) for (rint i = a; i <= b; i += c)
#define FLw(i, a, b, c) for (rint i = a; i >= b; i -= c)
#define min(a, b) (a)>(b)?(b):(a)
#define max(a, b) (a)>(b)?(a):(b)
#define Mod 1000000007
#define ll long long
#define MAXN 100005
#define MAXM 105
using namespace std;

inline int read()
{
    rint x = 0, f = 1;register char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9')x = x*10 + c-'0', c = getchar();
    return f*x;
}

int n, k, f[MAXN][MAXM][2][2], size[MAXN];
ll g[MAXM][2][2];

vector < int > e[MAXN];

inline int mod (int &a, ll b){return (a+(int)(b%Mod)%Mod)%Mod;}

void dfs (int u, int fa)
{
    rint v;
    size[u] = 1;
    f[u][0][0][0] = f[u][1][1][0] = 1;
    For (i, 0, e[u].size()-1)
        if ((v = e[u][i]) != fa)
        {
            dfs (v, u);
            For (i, 0, min(size[u], k)) g[i][0][0]=f[u][i][0][0],f[u][i][0][0]=0,g[i][0][1]=f[u][i][0][1],f[u][i][0][1]=0,g[i][1][0]=f[u][i][1][0],f[u][i][1][0]=0,g[i][1][1]=f[u][i][1][1],f[u][i][1][1]=0;
            For (i, 0, min(size[u], k))
                For (j, 0, min(size[v], k-i))
                    f[u][i+j][0][0]=mod(f[u][i+j][0][0],(ll)g[i][0][0]*(ll)f[v][j][0][1]),f[u][i+j][1][0]=mod(f[u][i+j][1][0],(ll)g[i][1][0]*(ll)(f[v][j][0][0]+f[v][j][0][1])),f[u][i+j][0][1]=mod(f[u][i+j][0][1],(ll)g[i][0][0]*(ll)f[v][j][1][1]+(ll)g[i][0][1]*(ll)(f[v][j][0][1]+f[v][j][1][1])),f[u][i+j][1][1]=mod(f[u][i+j][1][1],(ll)g[i][1][0]*(ll)(f[v][j][1][1]+f[v][j][1][0])+(ll)g[i][1][1]*(ll)((ll)(f[v][j][0][0]+f[v][j][0][1])+(ll)(f[v][j][1][1]+f[v][j][1][0])));
        size[u] += size[v];
        }
}

int main ()
{
    n = read(), k = read();
    For (i, 1, n-1)
    {
        rint a = read(), b = read();
        e[a].push_back(b), e[b].push_back(a);
    }
    dfs (1, 0);
    printf ("%d", (f[1][k][0][1]+f[1][k][1][1])%Mod);
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。