All Tracks Algorithms Graphs Problem

Absolute tree
Tag(s):

Algorithms, Depth-first search, Euler Tour and Path, Graphs, Segment tree

Problem
Editorial
Analytics

You are given a tree of size \(N\). The tree isrooted at \(1 \) and each node \(i\ (1 \le i\le N)\) contains a value \(A_i\).

You are also given an array \(K \) of size \(N\). For each node \(i\ (1 \le i\le N)\), you are required to determine the distance to the closest node \(j\) in the subtree of \(i\) such that \(\mid A_i - A_j \mid \ge K_i\).

Note

  • Distance between two nodes is calculated as the shortest path between them and it is represented as the number of edges
  • \(i \) also lies in its subtree

Input format

  • First line: An integer \(N\)
  • Second line: \(N\) space-separated integers denoting the elements of \(A \)
  • Third line: \(N\) space-separated integers denoting the elements of \(K\)
  • Next \(N-1 \) lines: Two integers \(u \) and \(v \) \((1 \le u,v \le N , u!=v)\) denoting an edge between them

Output format

Print \(N\) lines representing the answer. Here, \(i^{th}\) line contains the distance to the closest node \(j\) in subtree \(i \) that satisfies the condition. If no nodes satisfy the condition, then print \(-1\).

Constraints

\(1 \le N \le 200000\)

\(1 \le A_i \le 10^9\)

\(0 \le K_i \le 10^9\)

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

For node 1, the only valid candidate is node 3 since \(| A_1-A_3|\ge K_1\), so the answer is distance between nodes 1 and 3 which is 2.

For node 2, the valid candidates are node 2, and node 3, so the minimum of the distances from 2 is 0.

For node 3, there are no valid candidates, so the answer is -1.

Time Limit: 5,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

This Problem was Asked in

HackerEarth

Challenge Name

October Easy' 19

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?