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 ans = 0;
  9.  
  10. void DFS(int node , vector<int> G[] , int used[] , int parent[] , int k){
  11. 	used[node]=1;
  12. 	sum += val[node];
  13. 	int x = ((sum % k) + k) % k;
  14. 	ans += mpp[x];
  15. 	mpp[x]++;
  16.  
  17. 	for(auto u:G[node]){
  18. 		if(used[u]==0){
  19. 			parent[u] = node;
  20. 			DFS(u,G,used,parent,k);
  21. 		}
  22. 	}
  23.  
  24. 	sum -= val[node];
  25. 	mpp[x]--;
  26. }
  27.  
  28. int main() {
  29.  
  30. 	int n ; 
  31.     cin>>n ; 
  32.     vector <int> G[n+1];
  33.  
  34.     int i = 1 ; 
  35.     while(i<=n-1){
  36.         int u,v;
  37.         cin>>u>>v ; 
  38.         G[u].push_back(v);
  39.         G[v].push_back(u); 
  40.         i++;
  41.     }
  42.  
  43.     for(int i=1;i<=n;i++){
  44.     	cin>>val[i];
  45.     }
  46.     int k;
  47.     cin>>k;
  48.     int used[n+1] = {0};
  49.     int parent[n+1] = {0};
  50.     mpp[0] = 1;
  51.     DFS(1,G,used,parent,k); //starts from node 1
  52.     cout<<ans<<endl;
  53.     return 0;
  54. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
6
1 2
1 4
2 3
4 5
5 6
2 2 1 1 2 2
3
stdout
copy 
3
https://ideone.com/qXSWbm
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!