求这个代码的时间复杂度
  • 板块学术版
  • 楼主OldDriverTree
  • 当前回复10
  • 已保存回复11
  • 发布时间2023/12/16 22:11
  • 上次更新2023/12/17 09:06:05
查看原帖
求这个代码的时间复杂度
681036
OldDriverTree楼主2023/12/16 22:11

rt

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int N=5002;
vector<int> G[N];
int n,f[N][N],g[N][N];
int t[N],siz[N];

void dfs(int u,int fa)
{
	siz[u]=f[u][1]=g[u][0]=1;
	for (int v:G[u]) if (v^fa)
	{
		dfs(v,u);
		for (int i=0;i<=siz[u];i++) for (int j=0;j<=siz[v];j++)
		t[i+j]=(t[i+j]+1ll*(f[v][j]+g[v][j])%mod*g[u][i]%mod)%mod;
		for (int i=0;i<=siz[u]+siz[v];i++) g[u][i]=t[i],t[i]=0;
		for (int i=0;i<=siz[u];i++) for (int j=0;j<=siz[v];j++)
		t[i+j]=(t[i+j]+(1ll*f[u][i]*g[v][j]%mod+1ll*f[u][i]*f[v][j+1]%mod)%mod)%mod;
		for (int i=0;i<=siz[u]+siz[v];i++) f[u][i]=t[i],t[i]=0; siz[u]+=siz[v];
	}
}
int main()
{
	scanf("%d",&n);
	for (int i=1,x,y;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs(1,0);
	for (int i=1;i<=n;i++)
	printf("%d\n",(f[1][i]+g[1][i])%mod);
	return 0;
}
2023/12/16 22:11
加载中...