README.md

Covid-Crisis

Problem Statement -
ROOT2 Industries is a huge business firm. However, recently it has been hit hard by the fall of the market due to COVID - 19 and is almost on its way to bankruptcy. In order to prevent this the firm has decided to cut loose some of its departments. The departments in the firm have a hierarchical structure (with the Head Office at the root). Each department can have one or more sub-departments but each sub-department will have only one super-department. You have the details about the working costs and revenue generated by each department. The firm has to cut loose some of its departments, but if a department is cut loose, all its sub-departments are also dissolved, firing all the people working in them. Any department can be dissolved only by a department which lies in the hierarchical path from the department to the head office. Also a department can be dissolved by some other department only if the department (which is dissolving) has strictly better performance than the department being dissolved.

Performance of a department is determined by (Revenue Generated - Working Costs) of the department.

You have to write a program to find the departments which need to be fired and the corresponding department which will fire it in order to maximize the overall performance of the firm. If a department can be fired by multiple departments, output the department closest to it in the hierarchical structure. If there are multiple answers, print the one that requires the minimum number of departments to be fired explicitly.

*All the departments that need to be fired are fired simultaneously.
*Dissolve / Cut-loose / Fire all mean the same thing for the purpose of this question and are used interchangeably.

Input -
First line will contain a single integer n, number of departments in the ROOT2 firm.
The next line contains n space-separated integers w₁, w₂ , …, w_n representing the working costs of each department, where w_i represents the working cost of the i^th department.
The next line contains n space-separated integers r₁ , r₂ , …, r_n representing the revenue generated by each department, where r _i represents the revenue generated by i^th department.
The next n-1 lines contain 2 integers u and v, describing that department v is a sub-department of department u.

Output -
Print on a single line k - number of departments that need to be dissolved to maximize the performance of the firm.
On each of the next k lines, print the number of the department that needs to be dissolved and the number of the department that dissolves it.

Note - Print these k lines in the ascending order sorted by the number of the department getting dissolved.

Constraints -
0 < n <= 1000
0 <= wi, ri <= 100000
1 <= u, v <= n

Sample Input 1-
5
100 400 50 200 10
200 50 100 300 20
1 2
1 3
2 4
2 5

Sample Output 1-
1
2 1

Sample Input 2-
7
100 12 19 64 32 22 23
93 97 40 24 29 58 57
1 7
7 6
6 3
6 5
3 2
1 4

Sample Output 2-
2
4 1
5 6