救命,第四个点T了,好像是输出的锅

回复帖子

@Soknock 2020-10-07 22:06 回复

RT 前面dfs卡时测试了一遍,发现好像是后面输出的锅

不懂 求教QAQ

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

#define N 150005
#define MOD 1000000007
#define ull long long
#define rg register
using namespace std;
int n,k,x,y,siz[N],timeblock;
int dp[N][105][2][2],g[N][105][2];
vector<int>e[N];

inline int tmod(ull a,ull b){
    ull x=a%MOD,y=b%MOD;
    return (int)(x+y)%MOD;
}

void dfs(int u,int fa){
    siz[u]=1;
    for(vector<int>::iterator a=e[u].begin();a!=e[u].end();a++){
        int v=*a;
        if(v==fa)continue;
        dfs(v,u);
        siz[u]+=siz[v];
        for(rg int a=0;a<=min(siz[u],k);a++){
            g[a][0][0]=dp[u][a][0][0]%MOD;dp[u][a][0][0]=0;
            g[a][0][1]=dp[u][a][0][1]%MOD;dp[u][a][0][1]=0;
            g[a][1][1]=dp[u][a][1][1]%MOD;dp[u][a][1][1]=0;
            g[a][1][0]=dp[u][a][1][0]%MOD;dp[u][a][1][0]=0;
        }
        for(rg int a=0;a<=min(k,siz[u]);a++){
            for(rg int b=0;b<=min(k-a,siz[v]);b++){
                dp[u][a+b][0][0]=tmod(dp[u][a+b][0][0],(ull)dp[v][b][0][1]*(ull)g[a][0][0]);
                dp[u][a+b][1][0]=tmod(dp[u][a+b][1][0],(ull)g[a][1][0]*((ull)dp[v][b][0][0]+(ull)dp[v][b][0][1]));
                dp[u][a+b][0][1]=tmod(dp[u][a+b][0][1],(ull)g[a][0][1]*((ull)dp[v][b][0][1]+(ull)dp[v][b][1][1]));
                dp[u][a+b][0][1]=tmod(dp[u][a+b][0][1],(ull)g[a][0][0]*(ull)dp[v][b][1][1]);
                dp[u][a+b][1][1]=tmod(dp[u][a+b][1][1],(ull)g[a][1][0]*((ull)dp[v][b][1][0]+(ull)dp[v][b][1][1]));
                dp[u][a+b][1][1]=tmod(dp[u][a+b][1][1],(ull)g[a][1][1]*((ull)dp[v][b][0][0]+(ull)dp[v][b][0][1]+(ull)dp[v][b][1][1]+(ull)dp[v][b][1][0]));
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&k);
    for(rg int a=1;a<=n-1;a++){
        scanf("%d%d",&x,&y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    for(rg int a=1;a<=n;a++)
        dp[a][0][0][0]=dp[a][1][1][0]=1;
    dfs(1,-1);
    cout<<(dp[1][k][0][1]+dp[1][k][1][1])%MOD;
    return 0;
}
@Soknock 2020-10-09 16:44 回复 举报

@lxy__

感谢感谢QAQ

a枚举的应该是更新前的子树,所以子树大小更新要放在后面

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



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