陶陶的难题II

给定一棵包含 $N$ 个结点的树，每个结点 $i$ 有四个正实数 $x_i,y_i,p_i,q_i$。

对于每次询问 $a,b$，设 $S(a,b)$ 为树上从结点 $a$ 到结点 $b$ 的简单路径上的所有结点（包含两个端点）。在 $S(a,b)$ 中独立选择结点 $u,v$，允许 $u=v$，求：

$$\max_{u,v\in S(a,b)}\frac{y_u+q_v}{x_u+p_v}.$$

输入格式

第一行包含一个正整数 $N$，表示树中结点的个数。

第二行包含 $N$ 个正实数，第 $i$ 个数表示 $x_i$。

第三行包含 $N$ 个正实数，第 $i$ 个数表示 $y_i$。

第四行包含 $N$ 个正实数，第 $i$ 个数表示 $p_i$。

第五行包含 $N$ 个正实数，第 $i$ 个数表示 $q_i$。

接下来 $N-1$ 行，每行包含两个正整数 $a,b$，表示树中连接结点 $a$ 与结点 $b$ 的一条边。

第 $N+5$ 行包含一个正整数 $M$，表示询问个数。

最后 $M$ 行，每行包含两个正整数 $a,b$，表示一次询问。

所有 $x_i,y_i,p_i,q_i$ 的小数部分至多包含 $4$ 位。

输出格式

输出共 $M$ 行，每行包含一个实数。第 $i$ 行表示第 $i$ 次询问的答案。

若输出结果与标准答案的绝对误差不超过 $0.001$，则视为答案正确。

样例输入

5
3.0 1.0 2.0 5.0 4.0
5.0 2.0 4.0 3.0 1.0
1.0 3.0 2.0 4.0 5.0
3.0 4.0 2.0 1.0 4.0
1 2
1 3
2 4
2 5
4
2 3
4 5
2 4
3 5

样例输出

2.5000
1.5000
1.5000
2.5000

数据范围

• $1\le N,M\le 3\times 10^4$；
• $1\le x_i,y_i,p_i,q_i\le 10^8$；
• 对于每条边及每次询问，$1\le a,b\le N$；
• 所有 $x_i,y_i,p_i,q_i$ 均为正实数，小数部分至多包含 $4$ 位。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

5
3.0 1.0 2.0 5.0 4.0
5.0 2.0 4.0 3.0 1.0
1.0 3.0 2.0 4.0 5.0
3.0 4.0 2.0 1.0 4.0
1 2
1 3
2 4
2 5
4
2 3
4 5
2 4
3 5

输出

2.5000
1.5000
1.5000
2.5000