Let C[i][j] be weight of the edge( i, j). A( n, k ) - maximal amount of apples under k-th node after n cuts. B(k) - amount of edges under k-th node. Then ( k+ - right child and k-  - left child of the k-th nod )

A(n,k) = max{ a(n - B(k-), k+ ), if ( n > B(k-))                              }
            { a(n - B(k+), k- ), if ( n > B(k+))                              }                                                                           .           { MAX i FROM( 0) TO (n) OF a(n-i,k+)+a(i,k-) + C[k][k-]+C[k][k+]  }
            { A(0,k+) + A(0, k- ) + C[k][k-]+C[k][k+], if n = 0               }
            { - MAXAMOUNTOFAPPLES, if (k+ or k- doesn't exist AND n>0)        }

1-th and 2-th lines: one can cut left or rigth edge, if so we have to cut n-B(k+-) edges in the other subtree.

3-th line:           one can save both left and right edges, if so we have to cut i edges in left and n-i edges in the rigth subtrees. Choose maximal value changing i variable.

4-th line:           in this case we should count amout of apples under k-th node. It's equal to amount of apples in subtrees plus edge weights.

5-th line:           k is a leaf. if n>0 there is nothing to cut => deny this situation by MAXAMOUNTOFAPPLES with negative sign. I used MAXAMOUNTOFAPPLES  = 3000000

After that -  DP.

Can you write it on russian?