--n--'s blog

By --n--, history, 8 days ago, In English

Please help me solving this problem. I am not getting any idea how to proceed.

You are given an undirected weighed tree with N node . You need to find maximum absolute path sum in the tree with atmost k inversions. In one inversion you can change the weight of an edge from negative to positive and vice versa.

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by --n-- (previous revision, new revision, compare).

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I think state would be like this : dp[i][j] is the maximum path sum if we are at some node i and have already seen j inversions.

Maybe Tree Dp will help.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please give the link of problem?

»
8 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I solved it in O(n^3), n^2 dp considering one node as root, and O(n^3) by considering every node as root and choosing maximum from them,

My O(n^3) code
Some testcases and ans

But i believe n^2 solution is possible with rerooting DP, i tried that also but I'm somewhat confused in one concept of it

  • »
    »
    7 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    no need for rerooting just maintain root to the certain node using $$$X$$$ inversions max possible answer similarly do for children and then chose appropriately. either it could be child-child or child-ancestor for best path sum.

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    bro we need to find maximum absolute path sum

    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think that's what i wrote , the solution is just one abs() function call away

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you provide link for the question of this problem