求助,为什么全输出是零
查看原帖
求助,为什么全输出是零
1406403
dahao_667楼主2025/7/30 19:29
#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int xx,yy,n,K;
int dp[100003][103][3][3];
int lim[100003];//limit
int g[100003][3][3];
vector<int> v[100005];
void dfs(int x,int fa)
{
	dp[x][0][0][0]=1;
	dp[x][1][1][0]=1;
	lim[x]=1;
	int f;
	for(f=0;f<v[x].size();++f)
	{
		if(v[x][f]!=fa)
		{
			dfs(v[x][f],x);
			int Lim=min(lim[x]+lim[v[x][f]],K);
			for(int i=0;i<=lim[x];++i)
				for(int j=0;j<=lim[v[x][f]]&&(i+j)<=Lim;++j)
				{
					for(int p1=0;p1<2;++p1)
						for(int q1=0;q1<2;++q1)
							for(int p2=0;p2<2;++p2)
								for(int q2=0;q2<2;++q2)
									if(p1||q2) 
										g[i+j][p1][q1||p2]=(1ll*dp[x][i][p1][q1]*dp[v[x][f]][j][p2][q2]%mod)%mod;
				}
			for(int k=0;k<=Lim;++k)
				for(int p=0;p<2;++p)
					for(int q=0;q<2;++q)
						dp[x][k][p][q]=g[k][p][q];
			for(int k=0;k<=Lim;++k)
				g[k][0][0]=g[k][1][0]=g[k][0][1]=g[k][1][1]=0;
			lim[x]=Lim;
		}
	}
	return ;
}
int main()
{
	scanf("%d%d",&n,&K);
	for(int i=1;i<n;++i)
	{
		scanf("%d%d",&xx,&yy);
		v[xx].push_back(yy);
		v[yy].push_back(xx);
	}
	dfs(1,0);
	printf("%d",(dp[1][K][0][1],dp[1][K][1][1])%mod);
	return 0;
}
2025/7/30 19:29
加载中...