SHARE
TWEET

fun

sacgajcvs Jul 19th, 2019 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. 5 5
  3. 1 2
  4. 2 3
  5. 3 5
  6. 2 4
  7. 12 18 8 2 6
  8. 8
  9. 24
  10. 1
  11. 5
  12. 16
  13.  _____ _             _              _           _
  14. |_   _| |__   ___   / \   _ __  ___| |__  _   _| |
  15.   | | | '_ \ / _ \ / _ \ | '_ \/ __| '_ \| | | | |
  16.   | | | | | |  __// ___ \| | | \__ \ | | | |_| | |
  17.   |_| |_| |_|\___/_/   \_\_| |_|___/_| |_|\__,_|_|                                                
  18.  
  19. */
  20. #include<bits/stdc++.h>
  21. #define ll          long long
  22. #define pb          push_back
  23. #define    endl        '\n'
  24. #define rep(i,a,b)    for(ll int i=a;i<b;i++)
  25. #define vi          vector<ll int>
  26. #define all(a)      (a).begin(),(a).end()
  27. #define F           first
  28. #define S           second
  29. #define sz(x)       (ll int)x.size()
  30. using namespace std;
  31.  
  32. #define N 100005
  33. #define M 1000005
  34.  
  35. ll fact[M],v[N],hit[N],dp[M];
  36. bool vis1[M],vis[N];
  37. vi a[N];
  38. void prep()
  39. {
  40.     rep(i,2,M)
  41.     {
  42.         if(!vis1[i])
  43.         {
  44.             fact[i]=i;
  45.             for(ll j=2*i;j<M;j+=i)
  46.             {
  47.                 if(vis1[j]==0)
  48.                 {
  49.                     vis1[j]=1;
  50.                     fact[j]=i;
  51.                 }
  52.             }
  53.         }
  54.     }
  55. }
  56. void dfs(ll node)
  57. {
  58.     vis[node]=1;
  59.     for(auto i:a[node])
  60.     {
  61.         if(!vis[i])
  62.         {
  63.             hit[i]=hit[node]+1;
  64.             dfs(i);
  65.         }
  66.     }
  67. }
  68. ll fun(ll vl)
  69. {
  70.     if(vl==1)
  71.         return 1;
  72.     if(dp[vl]!=0)
  73.         return dp[vl];
  74.     vi tmp;
  75.     // cerr<<fact[vl];
  76.     ll pr=fact[vl],cnt=1;
  77.     vl/=fact[vl];
  78.     while(vl!=1)
  79.     {
  80.         if(fact[vl]==pr)
  81.         {
  82.             cnt++;
  83.         }
  84.         else
  85.         {
  86.             tmp.pb(cnt);
  87.             cnt=1;
  88.             pr=fact[vl];
  89.         }
  90.         vl/=fact[vl];
  91.     }
  92.     tmp.pb(cnt);
  93.     ll ans=1;
  94.     rep(i,0,sz(tmp))
  95.     ans*=(tmp[i]+1);
  96.     dp[vl]=ans;
  97.     return ans;
  98. }
  99. void solve()
  100. {
  101.     ll n;
  102.     cin>>n;
  103.     ll q;
  104.     cin>>q;
  105.     prep();
  106.     rep(i,1,n)
  107.     {
  108.         ll x,y;
  109.         cin>>x>>y;
  110.         a[x].pb(y);
  111.         a[y].pb(x);
  112.     }
  113.    
  114.     rep(i,1,n+1)
  115.     cin>>v[i];
  116.    
  117.     dfs(1);
  118.    
  119.     vector<pair<ll,pair<ll,ll>>> st(n);
  120.    
  121.     rep(i,1,n+1)
  122.     {
  123.         st[i-1].F=fun(v[i]);
  124.         st[i-1].S.F=-hit[i];
  125.         st[i-1].S.S=-i;
  126.     }
  127.    
  128.     sort(all(st));
  129.    
  130.     rep(i,0,q)
  131.     {
  132.         ll x;
  133.         cin>>x;
  134.         ll l=0,r=n;
  135.         while(l<=r)
  136.         {
  137.             ll mid=(l+r)/2;
  138.             if(fun(x)<=st[mid].F)
  139.             {
  140.                 r=mid-1;              
  141.             }
  142.             else
  143.                 l=mid+1;
  144.         }
  145.         if(l==0)
  146.             cout<<-1<<endl;
  147.         else
  148.             cout<<-st[l-1].S.S<<endl;
  149.     }
  150.     return;
  151. }
  152. int main()
  153. {
  154.     ios_base::sync_with_stdio(false);
  155.     cin.tie(0);
  156.     cout.tie(0);
  157.     int TESTS=1;
  158. //    cin>>TESTS;
  159.     while(TESTS--)
  160.     {
  161.         solve();
  162.     }
  163.     return 0;
  164. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top