nhphuc's blog

By nhphuc, history, 17 hours ago, In English

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
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Refer to trick 7 of this blog for more details.

»
11 hours ago, # |
  Vote: I like it -10 Vote: I do not like it

I don't know how to optimize such a thing, but I'm pretty sure trees are $$$unweighted$$$ so you might actually be talking about a tree-like graph.