Chemistry in Berland
Contest: Educational Codeforces Round 28
Difficulty rating: 2300
Tags: dfs and similar, greedy, trees

Igor is a post-graduate student of chemistry faculty in Berland State University (BerSU). He needs to conduct a complicated experiment to write his thesis, but laboratory of BerSU doesn't contain all the materials required for this experiment.

Fortunately, chemical laws allow material transformations (yes, chemistry in Berland differs from ours). But the rules of transformation are a bit strange.

Berland chemists are aware of n materials, numbered in the order they were discovered. Each material can be transformed into some other material (or vice versa). Formally, for each i (2 ≤ i ≤ n) there exist two numbers xi and ki that denote a possible transformation: ki kilograms of material xi can be transformed into 1 kilogram of material i, and 1 kilogram of material i can be transformed into 1 kilogram of material xi. Chemical processing equipment in BerSU allows only such transformation that the amount of resulting material is always an integer number of kilograms.

For each i (1 ≤ i ≤ n) Igor knows that the experiment requires ai kilograms of material i, and the laboratory contains bi kilograms of this material. Is it possible to conduct an experiment after transforming some materials (or none)?

Input format:
The first line contains one integer number n (1 ≤ n ≤ 105) — the number of materials discovered by Berland chemists.

The second line contains n integer numbers b1, b2... bn (1 ≤ bi ≤ 1012) — supplies of BerSU laboratory.

The third line contains n integer numbers a1, a2... an (1 ≤ ai ≤ 1012) — the amounts required for the experiment.

Then n - 1 lines follow. j-th of them contains two numbers xj + 1 and kj + 1 that denote transformation of (j + 1)-th material (1 ≤ xj + 1 ≤ j, 1 ≤ kj + 1 ≤ 109).

Output format:
Print YES if it is possible to conduct an experiment. Otherwise print NO.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3
1 2 3
3 2 1
1 1
1 1

Example output:
YES

Example input:
3
3 2 1
1 2 3
1 1
1 2

Example output:
NO

Editorial:
Since xi < i, then the transformation graph is a tree. Let's solve the problem recursively.
Suppose that material j is a leaf in the tree (there is no y such that xy = j). Then if we don't have enough material j, we have to transform some of material xj into j. Let's transform the amount required to set current amount of material j to aj; if we don't have the required amount of material xj, then this amount will temporarily be negative. And if we have more material j than we need to conduct the experiment, then we will transform it to xj. The same algorithm can be applied to any non-root node, but we first need to do this for all its children. This algorithm is optimal because each time we take the minimum possible amount from the parent.
After this the root will be the only node such that aj is not necessarily equal to current amount of material j. Since we solved the problem for all other materials and did it optimally, now the answer is YES iff current amount of material 1 is not less than a1.
This must be implemented carefully. Since the total amount of materials never increases, then if some material's current amount is less than, for example,  - 2·1017, then the answer is already NO. Also overflows in multiplication must be avoided; to do this, we can firstly check if the result of multiplication is not too big by multiplying values as real numbers.