#2402. 陶陶的难题II

陶陶的难题II

题目描述

最近陶陶在研究树的结构,某天他想出了一个看似简单的问题:

给出一颗 nn 个结点的树,树中每个结点有四个正实数参数值,第 ii 个结点的参数值分别用 xi,yi,pi,qix_i,y_i,p_i,q_i 表示。

给出 mm 次询问,每次询问给出两个点 a,ba,b ,设 i,ji,ja,ba,b 两点的树上路径上的任意两点(可以相同),要求回答 yi+qjxi+pj\frac{y_i + q_j}{x_i + p_j} 的最大值。

输入格式

第一行包含一个正整数 nn ,表示树中结点的个数。

第二行包含 nn 个正实数,第 ii 个数表示 xix_i

第三行包含 nn 个正实数,第 ii 个数表示 yiy_i

第四行包含 nn 个正实数,第 ii 个数表示 pip_i

第五行包含 nn 个正实数,第 ii 个数表示 qiq_i

接下来有 n1n-1行,每行包含两个正整数 a,ba,b ,表示结点 a,ba,b 之间有一条边。

n+5n+5 行包含一个正整数 mm ,表示询问次数。

最后 mm 行,每行包含正整数 a,ba,b ,表示一次询问。

输出格式

mm 行,每行一个实数,第 ii 行的数表示第 ii 次询问的答案。

只要你的输出和标准输出相差不超过 10310^{-3} 即认为正确。

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

数据规模与约定

对于 100%100\% 的数据 ,$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$ 。