为了账号安全,请及时绑定邮箱和手机立即绑定

想问为什么这个题只通过了50%的数据,然后就说我数组越界或者非法访问

/ 猿问

想问为什么这个题只通过了50%的数据,然后就说我数组越界或者非法访问

在星际争霸(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组数据。

对于每组数据:
第一行包含两个正整数n,q(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
4 4
1 5
10 100
200 50
66 88
1 1 2
1
2
3
4

输出

复制

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]);
   }
  }
  
 }
 
 
}


查看完整描述

目前暂无任何回答

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信