游酷盛世筆試第三題

感覺已經(jīng)使出了十八般武藝通過率還是0。。。

import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
public class Main {
  public static void main(String[] args) {
	  Scanner in = new Scanner(System.in);
	  int n = in.nextInt();
	  int[] vals = new int[n+1];
	  for(int i=1; i<=n; i++){
		  vals[i] = in.nextInt();
	  }
	  Map<Integer, Set<Integer>> mp = new HashMap<>();
	  for(int i=0; i<n-1; i++){
		  int t1 = in.nextInt();
		  int t2 = in.nextInt();
		  if(mp.get(t1)==null){
			  Set<Integer> st = new HashSet<>();
			  st.add(t2);
			  mp.put(t1, st);
		  }else{
			  Set<Integer> st = mp.get(t1);
			  st.add(t2);
		  }

		  if(mp.get(t2)==null){
			  Set<Integer> st = new HashSet<>();
			  st.add(t1);
			  mp.put(t2, st);
		  }else{
			  Set<Integer> st = mp.get(t2);
			  st.add(t1);
		  }
	  }

	  Deque<Integer> que = new LinkedList<>();
	  que.offerLast(1);
	  while(!que.isEmpty()){
		  int t = que.pollFirst();
		  if(mp.get(t)!=null){
			  for(int x:mp.get(t)){
				  Set<Integer> st = mp.get(x);
				  if(st!=null){
					  st.remove(t);
				  }
				  que.offerLast(x);
			  }
		  }
	  }

	  int q = in.nextInt();
	  while(q-->0){
		  int x = in.nextInt(), y = in.nextInt();
		  dost(vals, mp, x, y);
	  }

	  long[] res = new long[n+1];
	  int[] cnt = new int[n+1];
	  Arrays.fill(res, -1);
	  countMul(res, cnt, vals, mp, 1);
	  StringBuilder sb = new StringBuilder();
	  for(int i=1; i<n; i++){
		  // System.out.println(vals[i]+","+res[i]);
		  sb.append(cnt[i]);
		  sb.append(" ");
	  }
	  // System.out.println(vals[n]+","+res[n]);
	  sb.append(cnt[n]);

	  System.out.println(sb.toString());

  }

  public static int countZero(long[] a, int x){
	  String s = Long.toString(a[x]);
	  int sz = s.length();

	  int res = 0;
	  for(int i=0; i<sz; i++){
		  if(s.charAt(sz-i-1)=='0'){
			  res++;
			  a[x]/=10;
		  }else{
			  break;
		  }
	  }
	  return res;
  }

  public static void countMul(long[] res, int[] cnt, int[] vals, Map<Integer, Set<Integer>> mp, int x){
	  res[x] = vals[x];
	  cnt[x] += countZero(res, x);

	  if(mp.get(x)!=null){
		  for(int t:mp.get(x)){
			  if(res[t]==-1){
				  countMul(res, cnt, vals, mp, t);
			  }
			  res[x] *= res[t];
			  cnt[x] += countZero(res, x)+cnt[t];
		  }
	  }
  }

  public static void dost(int[] vals, Map<Integer, Set<Integer>> mp, int x, int y){
	  vals[x] *= y;
	  if(mp.get(x)!=null){
		  for(int t:mp.get(x)){
			  dost(vals, mp, t, y);
		  }
	  }
	  return;
  }
}