fork download 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Main
  9. {
  10. 	private static int sum = 0;
  11. 	private static int[] b;
  12. 	private static int m;
  13. 	private static HashMap<Integer, Integer> mpp;
  14. 	private static int cnt = 0;
  15.  
  16. 	public static void dfs(int node, ArrayList<Integer>[] adj, int[] used, int[] parent){
  17. 		used[node] = 1;
  18. 		sum += b[node];
  19. 		int k = sum%m;
  20. 		if(mpp.containsKey(k)){
  21. 			cnt += mpp.get(k);
  22. 		}
  23. 		mpp.put(k, mpp.getOrDefault(k,0)+1);
  24.  
  25. 		for(int child: adj[node]){
  26. 			if(used[child] == 0){
  27. 				parent[child] = node;
  28. 				dfs(child, adj, used, parent);
  29. 			}
  30. 		}
  31.  
  32. 		mpp.put(k, mpp.get(k) - 1);
  33. 		sum -= b[node];
  34. 	}
  35. 	public static void main (String[] args) throws java.lang.Exception
  36. 	{
  37. 		// your code goes here
  38. 		Scanner sc = new Scanner (System.in);
  39.  
  40. 		int n = sc.nextInt();
  41. 		ArrayList<Integer>[] adj = new ArrayList[n];
  42. 		for(int i=0;i<n;i++){
  43. 			adj[i] = new ArrayList<>();
  44. 		}
  45.  
  46. 		for(int i=0;i<n-1;i++){
  47. 			int u = sc.nextInt();
  48. 			int v = sc.nextInt();
  49. 			adj[u].add(v);
  50. 			adj[v].add(u);
  51. 		}
  52.  
  53. 		b = new int[n];
  54. 		for(int i=0;i<n;i++){
  55. 			b[i] = sc.nextInt();
  56. 		}
  57. 		m = sc.nextInt();
  58. 		mpp = new HashMap<>();
  59. 		mpp.put(0,1);
  60.  
  61. 		int[] used = new int[n];
  62. 		int[] parent = new int[n];
  63. 		dfs(0,adj,used,parent);
  64. 		System.out.println(cnt);
  65.  
  66. 	}
  67. }
Success #stdin #stdout 0.12s 54576KB
comments (?)
stdin 
6
0 1
1 2
0 3
3 4
4 5
2 2 1 1 2 2
2
stdout 
6
https://ideone.com/DNyBfJ
language:
Java (HotSpot 12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!