Code1

#include<iostream>
#include<cstdio>
using namespace std;
namespace do_while_true {
	int cnt=0;
	struct node {
		int to,next;
	}e[610];
	int n,m,f[310][310],head[310],v[310],siz[301],tot;
	void add(int x,int y) {
		e[++cnt].next=head[x];
		e[cnt].to=y;
		head[x]=cnt;
		e[++cnt].next=head[y];
		e[cnt].to=x;
		head[y]=cnt;
	}
	inline int read()
	{
		int r=0;
		char ch=getchar();
		while(ch<'0'||ch>'9')
			ch=getchar();
		while(ch>='0'&&ch<='9') {
			r=(r<<3)+(r<<1)+(ch^48);
			ch=getchar();
		}
		return r;
	}
	void dfs(int now,int fa) {
		siz[now]=1;
		for(int i=head[now];i;i=e[i].next) {
			if(e[i].to==fa) continue;
			dfs(e[i].to,now);
			siz[now]+=siz[e[i].to];
			for(int j=siz[now];j>=1;j--)
				for(int k=0;k<j;k++)
					f[now][j]=max(f[now][j],f[e[i].to][k]+f[now][j-k]);
		}
	}
	int main()
	{
		n=read();m=read();
		++m;
		for(int i=1;i<=n;i++) {
			int x=read();
			f[i][1]=read();
			add(x,i);
		}
		dfs(0,-1);
		printf("%d\n",f[0][m]);
		return 0;
	}
}
int main()
{
	return do_while_true::main();
}

Code2

#include<iostream>
#include<cstdio>
using namespace std;
namespace do_while_true {
	int cnt=0;
	struct node {
		int to,next;
	}e[610];
	int n,m,f[310][310],head[310],v[310],tot;
	void add(int x,int y) {
		e[++cnt].next=head[x];
		e[cnt].to=y;
		head[x]=cnt;
		e[++cnt].next=head[y];
		e[cnt].to=x;
		head[y]=cnt;
	}
	inline int read()
	{
		int r=0;
		char ch=getchar();
		while(ch<'0'||ch>'9')
			ch=getchar();
		while(ch>='0'&&ch<='9') {
			r=(r<<3)+(r<<1)+(ch^48);
			ch=getchar();
		}
		return r;
	}
	void dfs(int now,int fa) {
		for(int i=head[now];i;i=e[i].next) {
			if(e[i].to==fa) continue;
			dfs(e[i].to,now);
			for(int j=m;j>=1;j--)
				for(int k=0;k<j;k++)
					f[now][j]=max(f[now][j],f[e[i].to][k]+f[now][j-k]);
		}
	}
	int main()
	{
		n=read();m=read();
		++m;
		for(int i=1;i<=n;i++) {
			int x=read();
			f[i][1]=read();
			add(x,i);
		}
		dfs(0,-1);
		printf("%d\n",f[0][m]);
		return 0;
	}
}
int main()
{
	return do_while_true::main();
}

不同的地方是dfs的时候，Code1记录了点的子树大小，从子树大小为上界来dp，dp的复杂度是 ${siz_i}^2$。

Code2是直接 $m^2$ 的dp

Code2的时间复杂度我能算出来为 $\mathcal{O}(n^3)$也就是$\mathcal{O}(nm^2)$

Code1的复杂度大概是多少呢？机房大佬说是 $\mathcal{O}(n^2)$，求解qvq