fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. unordered_map<int,int>mpp;
  5.  
  6. int sum = 0;
  7. int val[1000000] = {0};
  8. int vlSubarrays = 0;
  9.  
  10. void dfs(int node , vector<int> adj[] , int used[] , int parent[] , int k){
  11.  
  12. 	used[node]=1;
  13.  
  14. 	sum += val[node];
  15. 	int x = sum % k;
  16. 	vlSubarrays+= mpp[x];
  17. 	mpp[x]++;
  18.  
  19. 	for(auto u:adj[node]){
  20. 		if(used[u]==0){
  21. 			parent[u] = node;
  22. 			dfs(u,adj,used,parent,k);
  23. 		}
  24. 	}
  25.  
  26. 	sum -= val[node];
  27. 	mpp[x]--;
  28. }
  29.  
  30. int main() {
  31.  
  32. 	int n ; 
  33.     cin>>n ; 
  34.     vector <int> adj[n+1];
  35.  
  36.     int i = 1 ; 
  37.     while(i<=n-1){
  38.         int u,v;
  39.         cin>>u>>v ; 
  40.         adj[u].push_back(v);
  41.         adj[v].push_back(u); 
  42.         i++;
  43.     }
  44.  
  45.     for(int i=1;i<=n;i++){
  46.     	cin>>val[i];
  47.     }
  48.     int k;
  49.     cin>>k;
  50.     int used[n+1] = {0};
  51.     int parent[n+1] = {0};
  52.     mpp[0] = 1;
  53.     dfs(1,adj,used,parent,k); 
  54.     cout<<"No of Valid Subarrays are: "<<vlSubarrays<<endl;
  55.     return 0;
  56. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
6
1 2
1 4
2 3
4 5
5 6
2 2 1 1 2 2
3
stdout
copy 
No of Valid Subarrays are: 3
https://ideone.com/ep8uWh
language:
C++ (gcc 8.3)
created:
3 days 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!