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...

## This Problem was Asked in

Challenge Name

October Easy' 19

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Number Theory
• Math > Basic Math
• Algorithms > Dynamic Programming
• Math > Basic Math
Уведомления

?