为什么老师说后者的时间复杂度是n的平方（或nm） 而前者却是n*m的平方呢？

我的：

#include<bits/stdc++.h>
using namespace std;
int n,m,fa,f[305][305];
int head[305],cnt;
struct EDGE{
	int nex,ver;
}edge[330];
void add(int x,int y)
{
	edge[++cnt].ver=y;edge[cnt].nex=head[x];
	head[x]=cnt;
}
int dfs(int now)
{
	for(int i=head[now];i;i=edge[i].nex)
	{
		dfs(edge[i].ver);
		for(int j=m+1;j>=1;j--)
			for(int k=0;k<j;k++)
				f[now][j]=max(f[now][j],f[edge[i].ver][k]+f[now][j-k]);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&fa,&f[i][1]);
		add(fa,i);
	}
	dfs(0);
	printf("%d",f[0][m+1]);
	return 0;
} 

老师的：

#include<bits/stdc++.h>
using namespace std;
const int N=301;
int n,m,a,b[N];
struct Edge {
	int v,nxt;
}edge[N<<1];
int head[N],idx;
int f[N][N],sum[N];
void add(int x,int y) {
	edge[++idx].v=y;
	edge[idx].nxt=head[x];
	head[x]=idx;
}
void dfs(int u) {
	f[u][1]=b[u];
    sum[u]=1;
	for(int i=head[u];i;i=edge[i].nxt) {
		int v=edge[i].v;
		dfs(v);
		for(int j=min(m+1,sum[u]+sum[v]);j>=0;j--) {
			for(int k=0;k<=min(sum[v],j-1);k++)
				f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]);
		}
        sum[u]+=sum[v];
	}
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) {
		scanf("%d%d",&a,&b[i]);
		add(a,i);
	} 
	dfs(0);
	printf("%d\n",f[0][m+1]);
	return 0;
}

其实我发现20MS的都是写后者的