I just have a problem like this: (source: VNOI)

• Given a tree with $$$n$$$ node(s), there will be $$$n - 1$$$ edge $$$(u, v, w)$$$ — edge from $$$u$$$ to $$$v$$$ with distance $$$w$$$. For $$$i$$$ from $$$1$$$ to $$$n$$$ you need to find $$$i$$$ node that path from $$$1$$$ to pass all chosen nodes is smallest. $$$n\leq 5000, w\leq 10^9$$$

I have a solution work in $$$O(n^3)$$$ like this:

for (int i = n; i >= 2; --i)
    for (int j = 1; j < i; ++j){
        dp[u][i][0] = min(dp[u][i][0], dp[u][i - j][0] + (dp[v][j][0] + w) * 2);
        dp[u][i][1] = min(dp[u][i][1], dp[u][i - j][1] + (dp[v][j][0] + w) * 2);
        dp[u][i][1] = min(dp[u][i][1], dp[u][i - j][0] + dp[v][j][1] + w);
    }

(with $$$v$$$ is a child node of $$$u$$$, full code here: https://ideone.com/Dz0dYV)

I dont know how to optimize from this to a $$$O(n^2)$$$, some of my friends told me that I should change the limit of $$$i$$$ to $$$sz(u)$$$ and $$$j$$$ to $$$sz(v)$$$ but I cant relize how it works. Please help me with this problem, thanks.

P/S: Sample test (in problem):

7
1 2 1
1 3 1
3 4 1
3 5 1
3 6 1
7 5 1

0
1
2
3
5
7
9