求助卡常QAQ

回复帖子

@huangzirui  2019-10-27 19:56 回复
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int i,j,k,n,m;
const int maxn=1e6+5;
char buffer[maxn],*S,*T; 
inline char Get_Char()  
{  
    if(S==T)  
    {  
        T=(S=buffer)+fread(buffer,1,maxn,stdin);
        if(S==T) return EOF;  
    }  
    return *S++;  
}
inline int read()
{
    char c;  
    int re=0;  
    for(c=Get_Char();c<'0'||c>'9';c=Get_Char());  
    while(c>='0'&&c<='9')  
           re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();  
    return re;  
}
void read(ll &x){
    char c;x=0;int b=1;do{c=getchar();if(c==45)b=-1;}while(c>57||c<48);
    do x=x*10+c-48,c=getchar();while(c<=57&&c>=48);x*=b;
}
const int mod=1000000007;
struct edge{
    int next,to,w;
}a[200011];
int head[100011],len;
inline void add(int x,int y){
    a[++len]={head[x],y};
    head[x]=len;
}
int dp[100011][111][2][2],g[111][2][2];
int Size[100011];
void dfs(int now,int fa){
    dp[now][0][0][0]=dp[now][1][1][0]=1;
    ++Size[now];
    for(register int i=head[now];i;i=a[i].next){
        int u=a[i].to;
        if(u==fa)continue;
        dfs(u,now);
        Size[now]+=Size[u];
        for(register int j=min(Size[now],m);j>=0;--j)
            for(register int k1=0;k1<=1;++k1)
                for(int k2=0;k2<=1;++k2){
                    g[j][k1][k2]=dp[now][j][k1][k2];
                    dp[now][j][k1][k2]=0;
                }
        for(register int j=min(m,Size[now]);j>=0;--j){
            for(register int k=0;k<=min(j,Size[u]);++k){
                int X1=(dp[u][k][0][0]+dp[u][k][0][1])%mod,X2=(dp[u][k][1][0]+dp[u][k][1][1])%mod;
                dp[now][j][0][0]+=(ll)g[j-k][0][0]*dp[u][k][0][1]%mod;
                if(dp[now][j][0][0]>mod)
                    dp[now][j][0][0]-=mod;
                dp[now][j][0][1]+=((ll)g[j-k][0][1]*((dp[u][k][0][1]+dp[u][k][1][1])%mod)%mod
                                  +(ll)g[j-k][0][0]*dp[u][k][1][1]%mod)%mod;
                if(dp[now][j][0][1]>mod)
                    dp[now][j][0][1]-=mod;
                dp[now][j][1][0]+=(ll)g[j-k][1][0]*X1%mod;
                if(dp[now][j][1][0]>mod)
                    dp[now][j][1][0]-=mod;
                dp[now][j][1][1]+=(((ll)g[j-k][1][1]*((X1+X2)%mod)%mod)%mod
                                   +(ll)g[j-k][1][0]*(dp[u][k][1][0]+dp[u][k][1][1]%mod)%mod)%mod;
                if(dp[now][j][1][1]>mod)
                    dp[now][j][1][1]-=mod;
            }
        }
    }
}
int main() {
    n=read();m=read();
    for(i=1;i<n;++i){
        int x,y;
        x=read();y=read();
        add(x,y);
        add(y,x);
    }
    dfs(1,0);
    cout<<(dp[1][m][0][1]+dp[1][m][1][1])%mod<<endl;
    cerr << 1.0*clock()/CLOCKS_PER_SEC << endl;
    return 0;
}

然而优化不了了 也不知道是不是写错了

QAQ QAQ QAQ

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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