How to solve ADASALES - Ada and Travelling Salesman.

general
, ,
1

spoj question http://www.spoj.com/problems/ADASALES/
how to solve this problem.

2

It can be done using in-out dp .

You can see Rachit Jain’s video tutorial,he has explained in-out dp concept nicely.

1 Like
3

can you please give the code.

4

Let A be array given in question.
For calculating in[] value: root tree at node 0.
if (A[child]-A[par]>0) then we can maximize in[par]=max(in[par],in[child]+(A[child]-A[par]))
This is in order to increase profit by using this edge.
For calculating out[] value:
we will find mx1,mx2 for every node which will have the value of in[child]+ { if (A[child]-A[par]>0) A[child]-A[par]}.
Thus mx will contain value of in[child] + if edge between parent and child gains profit .
Now we can find out[] value.
My code: https://ideone.com/od5toC