shahil_005

MATOM_cpp

Feb 22nd, 2021
83
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fastIO                  ios_base::sync_with_stdio(false);cin.tie(NULL);
  4. #define endl                    '\n'
  5. #define int long long
  6. #define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
  7.  
  8. #define time__(d) \
  9.     for ( \
  10.         auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); \
  11.         blockTime.second; \
  12.         debug("%s: %lld ms\n", d, chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false \
  13. )
  14. const long long N=(long long)(3e5+5);
  15. const long long M=(long long)(1e6);
  16. const long long MOD=(long long)(1e9+7);
  17.  
  18. vector<int> adj[N];
  19. bool vis[N];
  20. int a[N];
  21. int m[M+1];
  22. vector< pair<int,int> > ans(N);
  23.  
  24. bool prime[M+1];    
  25. void sieve()
  26. {
  27.     memset(prime, true, sizeof(prime));
  28.     prime[1]=false;
  29.     for (int p=2; p*p<=M; p++)
  30.     {
  31.         if (prime[p] == true)
  32.         {
  33.             for (int i=p*p; i<=M; i += p)
  34.                 prime[i] = false;
  35.         }
  36.     }
  37. }
  38. void precalculate(){
  39.     int x=2;
  40.     for(int i=2;i<=M;i++){
  41.         if(prime[i]){
  42.             x=i;
  43.             m[i]=x;
  44.         }
  45.         else{
  46.             m[i]=x;
  47.         }
  48.     }
  49. }
  50.  
  51. pair<int,int> dfs(int s, int par){
  52.     vis[s]=true;
  53.     int minv=m[a[s]];       //minimum energy
  54.     int cur=s;              //node with that minimum energy
  55.    
  56.     vector< pair<int,int> > v;
  57.     v.push_back({minv,cur});
  58.    
  59.     for(auto it:adj[s]){
  60.         if(!vis[it]){
  61.             pair<int,int> p=dfs(it,s);
  62.             v.push_back(p);
  63.         }
  64.     }
  65.    
  66.     sort(v.begin(),v.end());
  67.    
  68.     minv=(*v.begin()).first;    //minimum energy among all nodes in the subtree
  69.     cur=(*v.begin()).second;    //node with that minimum energy
  70.    
  71.     ans[s].first=cur;      
  72.     ans[s].second=(a[s]-minv); 
  73.    
  74.     return {minv,cur};      //return it to its parent
  75. }
  76. void solve()
  77. {
  78.     int n;
  79.     cin>>n;
  80.  
  81.     for(int i=1;i<=n;i++){
  82.         cin>>a[i];
  83.     }
  84.  
  85.     for(int i=1;i<=n-1;i++){
  86.         int x,y;
  87.         cin>>x>>y;
  88.         adj[x].push_back(y);
  89.         adj[y].push_back(x);
  90.     }
  91.  
  92.     sieve();
  93.     precalculate();
  94.     dfs(1,0);
  95.  
  96.     for(int i=1;i<=n;i++){
  97.         cout<<ans[i].first<<" "<<ans[i].second<<endl;
  98.     }
  99. }          
  100. int32_t main()
  101. {
  102.     fastIO
  103. // #ifndef ONLINE_JUDGE
  104.     // freopen("input.txt","r",stdin);
  105.     // freopen("output.txt","w",stdout);
  106. // #endif
  107.     int tc=1;
  108.     // cin>>tc;
  109.     while(tc--){
  110.             time__("solve"){
  111.                 solve();
  112.         }
  113.     }
  114.        
  115.         return 0;
  116. }
  117.  
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×