All Tracks Data Structures Disjoint Data Structures Basics of Disjoint Data Structures Problem

Still Maximum
Tag(s):

Easy

Problem
Editorial
Analytics

You are given a tree containing $$N$$ nodes(numbered from $$1$$ to $$N$$) and each node has a value associated with it. We define 'special value' of any graph as the maximum absolute difference of values of any two nodes such that there exists a path between them. Now you are given $$N-1$$ integers denoting that you have to delete ith edge at the ith step and find the 'special value' of the graph thus formed.

INPUT:

First line constains an integer $$N$$-number of nodes.
Next $$N-1$$ lines contains two integers $$u$$ $$v$$ denoting that there is a bidirectional edge between node $$u$$ and $$v$$
Next line contains $$N$$ integers ith of which is the value of node i.
Next $$N-1$$ lines contains an integer $$x$$ where the ith line denotes the index of the edge to be deleted at ith step.

Note: Every edge will be deleted exactly once.

OUTPUT:
Print $$N-1$$ lines where ith line should contain the 'special value' of the graph formed after deleting the edges of first i steps.

CONTRAINTS:
1 <= $$N$$ <= 105
0 <= value of each node <=109
1 <= $$u$$ , $$v$$ <= $$N$$
1 <= $$x$$ <= $$N-1$$

SAMPLE INPUT
3
1 2
2 3
1 2 3
2
1
SAMPLE OUTPUT
1
0
Explanation

In the 1st  first step edge between node number 2 and 3 is deleted so the maximum difference of values is between node number 1 and 2 which is 1.

After deleting edge between node 1 and 2 no two nodes are connected hence answer is 0.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications

?