20分求调
查看原帖
20分求调
1020359
29431_com楼主2024/5/16 13:23

只过了1.3两个测试点,第4个测试点超内存,其他全部WA,请问是哪个地方有问题导致WA的

#include<iostream>
#include<algorithm>
#include<vector>
const long long mod = (int)(1e9+7);
using namespace std;
int n,k;
struct edge
{
    int v,pre;
}E[200050];
int head[100010]={0};
int ssss = 1;
inline void add(int u,int v)
{
    E[ssss].v=v;
    E[ssss].pre = head[u];
    head[u] = ssss++;
}
int big[100010]={0};

int DP0[100010][110];
int DP1[100010][110];
int DP2[100010][110];
int DP3[100010][110];
void DFS(int now ,int fa)
{
    big[now]=1;
    int turn = 0;
    long long DP[2][110][2][2]={0};
    DP[turn][0][0][0]=1;
    DP[turn][1][1][0]=1;
    for(int x = head[now]; x; x = E[x].pre)// 当前边E[x]
    {
        if(E[x].v == fa)
            continue;
        
        DFS(E[x].v,now);
        for(int i = min(k,big[now] + big[E[x].v]) ; i >= 0 ; i--)
        {
            for(int j = max(i - big[now] , 0 ); j <= min(big[E[x].v],i) ; j++)
            {
                DP[turn^1][i][1][1] = (DP[turn^1][i][1][1]+
                   DP[turn][i-j][1][1] * (DP2[E[x].v][j] + DP3[E[x].v][j] + DP1[E[x].v][j] + DP0[E[x].v][j])
                 + DP[turn][i-j][1][0] * (DP2[E[x].v][j] + DP3[E[x].v][j])
                )%mod;

                DP[turn^1][i][1][0] = (DP[turn^1][i][1][0]+
                   DP[turn][i-j][1][0] * (DP1[E[x].v][j] + DP0[E[x].v][j])
                )%mod;

                DP[turn^1][i][0][0] = (DP[turn^1][i][0][0]+
                    DP[turn][i-j][0][0] * DP1[E[x].v][j]
                )%mod;

                DP[turn^1][i][0][1] = (DP[turn^1][i][0][1]+
                  DP[turn][i-j][0][1] * (DP3[E[x].v][j] + DP1[E[x].v][j])
                + DP[turn][i-j][0][0] * DP3[E[x].v][j]%mod
                )%mod;
            }
        }

        for(int i = 0 ; i <= k ;i++)
        {
            DP[turn][i][1][1]=0;
            DP[turn][i][0][1]=0;
            DP[turn][i][1][0]=0;
            DP[turn][i][0][0]=0;
        }
        turn = turn ^ 1;
        big[now] += big[E[x].v];
    }
    for(int i = 0 ; i <= k ;i++)
    {
        DP3[now][i]=DP[turn][i][1][1];
        DP1[now][i]=DP[turn][i][0][1];
        DP2[now][i]=DP[turn][i][1][0];
        DP0[now][i]=DP[turn][i][0][0];
    }
}
signed main()
{
    cin>>n>>k;
    for(int i = 0 ; i < n-1 ; i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    DFS(1,-1);
    cout<<(DP1[1][k]+DP3[1][k])%mod;
    return 0;
}
2024/5/16 13:23
加载中...