odd doctor 已更新

火花

Time Limit
1s
Memory Limit
262144KB
Judge Program
Standard
Ratio(Solve/Submit)
0.00%(0/2)
Description:

n个城市由n-1条边构成一棵树,首都编号为1。小Z喜欢收集各种各样的石头,i个城市的石头的粗糙度为p[i],鲜艳度为q[i],他发现城市i石头与城市j的石头相互摩擦发出的火花的美观度v=p[i]*p[j]+q[i]*q[j]询问小明从城市x出发向首都前进,每次经过一个城市就收集一块石头,从收集到的石头中选两个石头擦出的火花的最大美观度。

Input:

第一行给出一个整数T(1<=T<=5),表示测试数据的数目。
对于每组测试数据,

第一行是一个正整数n,m1<=n,q<=50000),表示城市个数和询问次数,

接下来一行n-1个数,依次表示城市2到城市n在树中的父亲城市编号,

接下来n行,每行两个数pq(0<=p,q<=30000)依次表示城市1到城市n的石头的粗糙度和鲜艳度,

接下m行,每行一个数x(2<=x<=n),询问从x出发到首都收集的石头能擦出的最大美观度。

Output:

对于每一组数据,

输出m行整数表示每次询问的答案。

Sample Input:
1
4 3
1 1 3
1 5
5 1
3 4
4 3
2
3
4
Sample Output:
10
23
24
Source:

hdu校赛


Submit