So Close Yet So Far
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Takaki Tono is a Computer Programmer in Tokyo. His boss at work shows him an online puzzle, which if solved would earn the solver a full expense paid trip to Los Angeles, California. Takaki really wants to solve this, as the love of his life, Akari, lives in Los Angeles and he hasn't met her since four years. Upon reading the puzzle he realizes that it is a query based problem. The problem is as follows :-
You are given a Tree T with N nodes numbered from 1 to N, with each node numbered z having a positive integer Az written on it. This integer denotes the value of the node. You have to process Q queries, of the following forms :-
1) C x y : Report the closest two values in the unique path from x to y i.e compute min(|Ap - Aq|) where p and q are two distinct nodes on the unique path from x to y.
2) F x y : Report the farthest two values in the unique path from x to y i.e. compute max(|Ap - Aq|) where p and q are two distinct nodes on the unique path from x to y.
It is also mentioned that x is not equal to y in any query and that no two nodes have the same value printed on them. Also, |x| denotes the absolute value of x.
Takaki is perplexed and requires your help to solve this task? Can you help him out?
The first line of the input contains an integer N denoting the number of nodes in tree T.
The second line comprises N space separated integers denoting A, where the i-th integer denotes Ai.
The next N-1 lines each comprise two space separated integers u and v, denoting that node u and node v are connected by an edge. It is guaranteed that the final graph will be a connected tree.
The next line contains a single integer Q, denoting number of queries.
The next Q lines comprise the queries. Each such line is of the format C x y or F x y.
For each query, print the required output as mentioned above.
- 2 ≤ N ≤ 35000
- 1 ≤ Ai ≤ 109
- 1 ≤ Q ≤ 35000
- 1 ≤ u, v ≤ N
- No two nodes have the same value printed on them.
- x is not equal to y in any query.
SubtasksSubtask #1 (15 points)
- N, Q ≤ 1000
- Only Type F queries are present.
- Original constraints
Input: 5 1 2 7 4 5 1 2 2 3 2 4 2 5 7 C 1 5 F 1 5 C 2 4 C 1 2 F 1 3 F 3 4 F 2 4 Output: 1 4 2 1 6 5 2
Given below is the tree corresponding to the sample input. Each node has two numbers written in it.
The first number represents the node index and the second number indicates node value.
|Tags||animesh_f, data-structure, ltime38, lunchtime, mo-algorithm, optimization|
|Time Limit:||3.5 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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.