在星际争霸(StarCraft)中有3个种族。对于任意一个种族他们的建筑建造都是有一个顺序的。这个顺序正好是一个树形结构我们称之为"科技树"(Technology tree)。
在科技树中只有一个建筑是不需要前置建筑的,我们把这个建筑的编号设为1其他的建筑,有且仅有一个前置建筑
比如建筑2的前置建筑为建筑1,意思是只有先建造了建筑1才能建造建筑2。
一个种族有n个建筑建筑1没有前置建筑,建筑i(2≤i≤n)的前置建筑为f每个建筑的建造都需要费用,建筑i(1≤i≤n)的建造花費为a晶体矿和b高能瓦斯
现在tokitsukaze想知道,如果想要建造建筑x总共需要消耗多少晶体矿和高能瓦斯。
第一行包含一个T(T≤10)表示T组数据。 第一荇包含两个正整数nq(1≤n,q≤20000),表示有n个建筑和q次查询 接下来n行,每行包含两个整数a,b(0≤a,b≤300)表示建造建筑i需要花费a晶体矿和b高能瓦斯。 接下來一行包含n-1个正整数f(1≤f≤n)。第i个(1≤i<n)正整数fi(1≤fi<i)表示建筑i+1的前置建筑为fi 接下来q行,每行包含一个正整数x表示询问。
对于每个询问輸出一行,包含两个整数c,d(用空格隔开)表示如果想要建造建筑x,总共需要消耗c晶体矿和d高能瓦斯
如果想要建造建筑1,总共需要消耗1晶体礦和5高能瓦斯 如果想要建造建筑2,需要先建造建筑1总共需要消耗1+10晶体矿和5+100高能瓦斯。 如果想要建造建筑3需要先建造建筑1,总共需要消耗1+200晶体矿和5+50高能瓦斯 如果想要建造建筑4,需要先建造建筑1和建筑2总共需要消耗1+10+66晶体矿和5+100+88高能瓦斯。
本来想用查找可是会超时,就換了这种在读入的时候就把前边需要的现加上这样后边就不用特殊处理了。