--n--'s blog

Max absolute path sum in a tree with atmost k inversions.
By --n--, history, 4 years 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

Comments Comments (3)
| Write comment?
»
4 years 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

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anyone tell what should the dp states be and the corresponding recurrence relation?

→ Reply