All submissions for this problem are available.
NASA is building a new super-computer. For this they are designing a new OS. All the processes that are running on the computer at a time are assigned an integer by the OS, which is called ’ factor ’. Each process has its own factor assigned to it. G(k) is a function which gives the factor of process k.
The running processes can be represented by the nodes of a tree. If process B is a descendant of process A in the tree, then B is called the sub-process of process A and A is called the super-process of B.At the root of the tree is Process ‘Top’. All the other processes are its sub-processes.
F(x,y) is a function which determines the performance of the super-computer. Here (x,y) is that pair of processes (y is always a sub-process of process x) where the difference between the factors of process x and process y is maximum. You are required to find maximum value of G(x)-G(Y) .
Each test case contains (2*N+1) integers. The first integer represents the number of running processes. The next N integers i.e A[i] give the factors(g(i) ) of process 1…. N. The last N integers give the super-processes of process 1….N.
If the super-process of a process is denoted by -1, it means that the process is at the root of the tree i.e. it is process ‘Top’.
You are required to find G(x) - G(Y), where x and y is that pair of processes (y is always a sub-process of process of x) where the difference between the factors of x and y is maximum..
- -10^8 ≤ a[i] ≤ 10^8
- 2 ≤ N ≤ 10^5
Input: 4 5 10 6 12 2 -1 4 2 Output: 6
|Tags||bfs, graph-theory, inlo2016, medium-hard, ravit0001|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions