DMOPC '21 Contest 1 P6 - Tree Jumping

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

Unfortunately, it turns out that a lot of the shows you've been watching this season haven't really lived up to their hype. To vent your frustration, you've decided to spend the weekend jumping in a tree instead.

The tree you're jumping in is rooted at node 1 with N nodes connected by N1 edges, the i-th edge connecting nodes ui and vi with a length of li. Each node i has 2 values ri and ci.

You may jump from node a to node b if b is a descendant of a and ra>cb, with a danger factor of dist(a,b)racb where dist(a,b) is the length of the shortest path from a to b.

For each node i from 2 to N, find the minimum danger factor of a direct jump from some node to node i or determine that it is impossible to jump to this node.

Constraints

2N3×105

1ri,ci,li109

1ui,viN

Subtask 1 [30%]

ui=i and vi=i+1 for all i.

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains an integer N.

The second line contains N integers ri (1iN).

The third line contains N integers ci (1iN).

The next N1 lines each contain 3 integers ui, vi, and li.

Output Specification

Output N1 lines, the i-th line containing the minimum danger factor of a direct jump from some node to node i+1 or Unreachable if it is impossible to jump to this node. Your output will be considered correct if the absolute or relative error of each numerical value does not exceed 109.

Sample Input

Copy
7
11 8 7 2 6 3 9
2 1 1 5 4 3 13
2 4 3
1 2 3
7 1 4
3 6 6
2 3 2
5 3 1

Sample Output

Copy
0.300000000000
0.285714285714
1.000000000000
0.333333333333
1.375000000000
Unreachable

Explanation

For node 2, it is best to jump from node 1 to node 2 with a danger factor of 3111=310.

For node 3, it is best to jump from node 2 to node 3 with a danger factor of 281=27.

For node 4, it is best to jump from node 1 to node 4 with a danger factor of 6115=1.

For node 5, it is best to jump from node 3 to node 5 with a danger factor of 174=13.

For node 6, it is best to jump from node 1 to node 6 with a danger factor of 11113=118.

For node 7, it is impossible to jump to this node.


Comments

There are no comments at the moment.