fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long int
  5.  
  6. vector<long int> vect[100001];
  7. ll val[100001];
  8. ll rem[100001];
  9. ll res[100001];
  10. vector<long int> leaf;
  11. long int n;
  12.  
  13. ll gcd(ll x,ll y){							// finding gcd of x and y.
  14.     if(y==0)
  15.         return x;
  16.     return gcd(y,x%y);
  17. }
  18.  
  19. // calculating the required answer for node (leaf) when the gcd of value of all the node from root to that node is x.
  20.  
  21. ll cal(ll x,long int node){
  22.     ll y=rem[node];
  23.     x=gcd(x,y);
  24.     return y-x;								// required answer would be maximum of (multiple of x)%m.
  25. }
  26.  
  27. // performing dfs in the tree where parent[x]=y and g is gcd of value of all the nodes from root to x.
  28.  
  29. void dfs(long int x,long int y,ll g){
  30.     g=gcd(g,val[x]);
  31.     long int sz=vect[x].size();
  32.     for(long int i=0;i<sz;++i){
  33.         if(vect[x][i]==y)
  34.             continue;
  35.         dfs(vect[x][i],x,g);
  36.     }
  37.     if(sz==1){							// sz=1 means it is a leaf node as it is connected to only 1 node.
  38.         if(x!=1){
  39.             leaf.push_back(x);
  40.             res[x]=cal(g,x);					// res array to store answer for each leaf node.
  41.         }
  42.     }
  43.     else if(sz==0 && n==1){
  44.         leaf.push_back(x);
  45.         res[x]=cal(g,x);
  46.     }
  47. }
  48.  
  49. int main(){
  50.     ios_base::sync_with_stdio(false);
  51.     cin.tie(NULL);
  52.     //freopen("input12.txt","r",stdin);
  53.     //freopen("output12.txt","w",stdout);
  54.     int t;
  55.     cin>> t;
  56.     while(t--){
  57.         //long int n;
  58.         cin>> n;
  59.         for(long int i=1;i<=n;++i)
  60.             vect[i].clear();
  61.         leaf.clear();
  62.         long int x,y;
  63.         for(long int i=1;i<n;++i){
  64.             cin>> x>> y;
  65.             vect[x].push_back(y);				// vect is used to construct adjacency matrix of the given tree.
  66.             vect[y].push_back(x);
  67.         }
  68.         for(long int i=1;i<=n;++i)
  69.             cin>> val[i];					// val array to store value of each node.
  70.         for(long int i=1;i<=n;++i)
  71.             cin>> rem[i];					// rem array to store m of each node.
  72.         dfs(1,1,val[1]);
  73.         sort(leaf.begin(),leaf.end());				// leaf vector to store leaf nodes.
  74.         long int sz=leaf.size();
  75.         for(long int i=0;i<sz;++i)
  76.             cout<< res[leaf[i]]<<" ";				// output the answer for each leaf node in increasing order of leaf node number.
  77.         cout<<"\n";
  78.     }
  79.     return 0;
  80. }
Success #stdin #stdout 0s 19928KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/U6TnNQ
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!