在星際爭霸(StarCraft)中，有3個種族。對于任意一個種族，他們的建筑建造都是有一個順序的。這個順序正好是一個樹形結(jié)構(gòu)，我們稱之為"科技樹"(Technology tree)。在科技樹中，只有一個建筑是不需要前置建筑的，我們把這個建筑的編號設(shè)為1。其他的建筑，有且僅有一個前置建筑。比如建筑2的前置建筑為建筑1，意思是只有先建造了建筑1，才能建造建筑2。一個種族有n個建筑，建筑1沒有前置建筑，建筑i(2≤i≤n)的前置建筑為f。每個建筑的建造都需要費用，建筑i(1≤i≤n)的建造花費為a晶體礦和b高能瓦斯?，F(xiàn)在tokitsukaze想知道，如果想要建造建筑x，總共需要消耗多少晶體礦和高能瓦斯。輸入描述:第一行包含一個T(T≤10)，表示T組數(shù)據(jù)。 對于每組數(shù)據(jù)： 第一行包含兩個正整數(shù)n，q(1≤n,q≤20000)，表示有n個建筑和q次查詢。 接下來n行，每行包含兩個整數(shù)a,b(0≤a,b≤300)，表示建造建筑i需要花費a晶體礦和b高能瓦斯。 接下來一行，包含n-1個正整數(shù)f(1≤f≤n)。第i個(1≤i＜n)正整數(shù)fi(1≤fi＜i)表示建筑i+1的前置建筑為fi。 接下來q行，每行包含一個正整數(shù)x，表示詢問。輸出描述:對于每個詢問，輸出一行，包含兩個整數(shù)c,d(用空格隔開)，表示如果想要建造建筑x，總共需要消耗c晶體礦和d高能瓦斯。示例1輸入復(fù)制 1 4?4 1?5 10?100 200?50 66?88 1?1?2 1 2 3 4輸出復(fù)制 1?5 11?105 201?55 77?193說明第一組樣例： 如果想要建造建筑1，總共需要消耗1晶體礦和5高能瓦斯。 如果想要建造建筑2，需要先建造建筑1，總共需要消耗1+10晶體礦和5+100高能瓦斯。 如果想要建造建筑3，需要先建造建筑1，總共需要消耗1+200晶體礦和5+50高能瓦斯。 如果想要建造建筑4，需要先建造建筑1和建筑2，總共需要消耗1+10+66晶體礦和5+100+88高能瓦斯。import java.util.*;public class Technology_tree {?static List<Integer> v[]; ?static int p[];?static int g[];?static int fa[];??static public void dfs(int u,int a,int b) {??p[u]+=a;??g[u]+=b;??if(v[u]!=null) {???for(int i=0;i<v[u].size();i++) {????int x=v[u].get(i);????dfs(x,p[u],g[u]);???}??}???}?public static void main(String[] args) {??// TODO 自動生成的方法存根??Scanner sc=new Scanner(System.in);??int T=sc.nextInt();??int n,q;??while(T--!=0) {???n=sc.nextInt();???q=sc.nextInt();???p=new int[n+1];???g=new int[n+1];???fa=new int[n+1];???v=new ArrayList[n+1];???for(int i=1;i<=n;i++) {????p[i]=sc.nextInt();????g[i]=sc.nextInt();???}???int w;//前置???for(int i=2;i<=n;i++) {????w=sc.nextInt();????fa[i]=w;????if(v[w]==null) {?????v[w]=new ArrayList<Integer>();????}????v[w].add(i);???}???dfs(1,0,0);???int s;???for(int i=0;i<q;i++) {????s=sc.nextInt();????System.out.println(p[s]+" "+g[s]);???}??}???}??}