#include <cstdio>
#include <algorithm>
// #define file
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define INPUT_DATA_TYPE int
#define OUTPUT_DATA_TYPE int

struct node{
    int to,next;
    node(){
        next=-1;
    }
}e[10010];

int head[10010],w[10010],f[10010][10010],cnt[10010],W,tot,times;

INPUT_DATA_TYPE read();
void print(OUTPUT_DATA_TYPE x);

void addEdge(int u,int v){
    e[tot].next=head[u];
    e[tot].to=v;
    head[u]=tot;
    ++tot;
    return;
}

void dfs(int u,int p){
    for(int i=head[u];~i;i=e[i].next){
        if(e[i].to==p) continue;
        dfs(e[i].to,u);
        cnt[u]+=cnt[e[i].to]+1;
        for(int j=min(cnt[u],W);~j;--j){
            for(int k=min(cnt[e[i].to],j-1);k>=0;--k)
                f[u][j]=max(f[u][j],f[u][j-k-1]+f[e[i].to][k]+w[e[i].to]),++times;
        }
    }
    return;
}

int main(){
	#ifdef file
	freopen("plan.in", "r", stdin);
	freopen("plan.out", "w", stdout);
	#else
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
    #endif

    register int i,t;
    int n=read();
    W=read();

    for(i=0;i<=n;++i) head[i]=-1;

    for(i=1;i<=n;++i){
        t=read();
        addEdge(t,i);
        w[i]=read();
    }

    dfs(0,0);

    printf("%d %d",f[0][W],times);

	#ifdef file
	fclose(stdin);
	fclose(stdout);
	#endif
    return 0;
}

INPUT_DATA_TYPE read(){
    register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();
    while(c<'0'||'9'<c)f=(c=='-'),c=getchar();//?=if,:=else
    while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return f?-x:x;
}

void print(OUTPUT_DATA_TYPE x){
    register char s[20];
    register int i=0;
    if(x<0){
        x=-x;
        putchar('-');
    }
    if(x==0){
        putchar('0');
        return;
    }
    while(x){
        s[i++]=x%10;
        x/=10;
    }
    while(i){
        putchar(s[--i]+'0');
    }
    return;
}

码风较丑，见谅。

本段代码用于解决体积都为1的树形背包问题。请问时间复杂度是 $O(n^2)$ 还是 $O(n^3)$

有的说法是树形背包时间复杂度是 $O(n^2)$ ，但是我实测一条链的时候是 $O(n^3)$。请问我的代码有什么问题吗？