树形背包！

树形背包的朴(wu)素(nao)操作的时间复杂度是n^3的，设有n个节点，背包容量为m(和n大小在一个级别上)

以01背包举例：

void dfs(int u){
    for(int i=head[u];i!=-1;i=edge[i].nxt){
        int v=edge[i].to;
        dfs(v);
        for(int i=m;i>=0;i--){
            int tmp=0;
            for(int j=0;j<=i;j++){
                tmp=max(tmp,dp[u][j]+dp[v][i-j]);
            }
            dp[u][i]=tmp;
        }
    }
}

上面的枚举显然是n^3的。。。

然而上面这种方法枚举到了很多还没有被转移过的无效状态，所以可以用siz数组优化。。。

代码如下：

void dfs(int u){
    for(int i=head[u];i!=-1;i=edge[i].nxt){
        int v=edge[i].to;
        dfs(v);
        for(int j=siz[u];j>=0;j--){
            int tmp=0;
            for(int k=0;k<=siz[v];k++){
                tmp=max(tmp,dp[u][j]+dp[v][k])
            }
            dp[u][j+k]=tmp;
        } 
        siz[u]+=siz[e];
    }
}

于是时间复杂度就降至n^2。。。

证明如下：

对于每个点对(i,j)，

只有在更新到LCA的时候才会出现一次，

所以对于每个点都是一个n，

总体就是n^2。。。

就酱。。。