In example we have:
7 soldiers
1 - commander
2 - Ki = 1, Ci = 10
3 - Ki = 2, Ci = 5
4 - Ki = 2, Ci = 3
5 - Ki = 3, Ci = 1
6 - Ki = 4, Ci = 2
7 - Ki = 5, Ci = 3
It's right?
Now, by a problem A1 === 1, A5 = A6 = A7 === 0.
A2, A3 and A4 - may be either 0 or 1, yes?
if A2 = 1 and A3 = 0 and A4 = 1 then profit = C7 * |A7 - A3| + C6 * |A6 - A3| + C5 * |A5 - A3| + C4 * |A4 - A2| + C3 * |A3 - A2| + C2 * |A2 - 1| = 3 * 0 + 2 * 0 + 1 * 0 + 3 * 0 + 5 * 1 + 10 * 0 = 5
Then answer min profit = 5.
But in example is 8.00
I understood! 4 - it's soldier too and his A4 === 0 too

Edited by author 25.03.2016 21:20

My multitest has fallen at this test. I got AC when deleted it.
Please, clear it from some trash in the end.

Observe than A[i] must be equal 0 or 1 ( no double ).
Just compute dp[v]. dp[v] is cost of traffic of subTree with root v if A[v] = 1.
If A[v]=0 than cost(of traffic of subTree with root v) equals zero.

Edited by author 03.09.2013 01:58

Edited by author 03.09.2013 01:59

" It is a tradition that a subordinate's computer has number that is greater than the number of his commander's computer. Each military person"  why there are some ki > i ? in th 9th case, isn't it a tree with the root 1?

What is the minimal value for Ai?

WA9,help please.