fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define int long long
  5.  
  6. const int mod=1e9+7;
  7. const int mxn=1e6+7;
  8. int n,q,dd[mxn],check[mxn],res[mxn],dp[mxn];
  9. typedef pair<int,int>ii;
  10. vector<int>val;
  11. int query[mxn],a[mxn];
  12. vector<int>g[mxn];
  13. vector<int>team[mxn];
  14. int dfs(int u,int p)
  15. {
  16.     check[u]=true;
  17.     int res=1;
  18.     for(auto v:g[u])
  19.     {
  20.         if(v!=p&&!check[v]&&dd[v])
  21.         {
  22.             res=res*((dfs(v,u)+1)%mod)%mod;
  23.         }
  24.     }
  25.     dp[u]=res;
  26.     return res;
  27. }
  28. signed main()
  29. {
  30.     cin>>n;
  31.     for(int i=1;i<=n;i++)
  32.     {
  33.         cin>>a[i];
  34.         val.push_back(a[i]);
  35.     }
  36.     for(int i=1;i<n;i++)
  37.     {
  38.         int u,v;
  39.         cin>>u>>v;
  40.         g[u].push_back(v);
  41.         g[v].push_back(u);
  42.     }
  43.     cin>>q;
  44.     for(int i=1;i<=q;i++)
  45.     {
  46.         cin>>query[i];
  47.         val.push_back(query[i]);
  48.     }
  49.     sort(val.begin(),val.end());
  50.     val.resize(unique(val.begin(),val.end())-val.begin());
  51.     for(int i=1;i<=n;i++){
  52.         a[i]=lower_bound(val.begin(),val.end(),a[i])-val.begin()+1;
  53.         team[a[i]].push_back(i);
  54.     }
  55.     for(int i=1;i<=q;i++)
  56.         query[i]=lower_bound(val.begin(),val.end(),query[i])-val.begin()+1;
  57.     int prev=0;
  58.     for(int v=val.size()-1;v>=0;v--)
  59.     {
  60.         int t=v+1;
  61.         if(!team[t].empty())
  62.         {
  63.             int sum=0;
  64.             for(auto u:team[t])
  65.             {
  66.                 dd[u]=true;
  67.             }
  68.             for(int i=1;i<=n;i++)
  69.             {
  70.                 check[i]=false;
  71.                 dp[i]=0;
  72.             }
  73.             for(int i=1;i<=n;i++)
  74.             {
  75.                 if(!check[i]&&dd[i])
  76.                 {
  77.                     dfs(i,i);
  78.                 }
  79.             }
  80.             for(int i=1;i<=n;i++)
  81.                 sum=(sum+dp[i])%mod;
  82.             res[t]=((sum-prev)%mod+mod)%mod;
  83.             prev=sum;
  84.         }
  85.     }
  86.     for(int i=1;i<=q;i++)
  87.         cout<<res[query[i]]<<"\n";
  88.     return 0;
  89. }
  90. /*
  91. 4
  92. 2 4 3 1
  93. 4 3
  94. 4 2
  95. 4 1
  96. 4
  97. 1
  98. 2
  99. 3
  100. 4
  101. */
  102.  
Success #stdin #stdout 0.02s 61032KB
comments (?)
stdin 
4
2 4 3 1
4 3
4 2
4 1
4
1
2
3
4
stdout 
8
1
1
1
https://ideone.com/wtVMSG
language:
C++14 (gcc 8.3)
created:
6 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!