fork download
copy 
  1. #include<bits/stdc++.h>
  2. #pragma GCC optimize("O3,unroll-loops")
  3. #define maxn 50005
  4. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  5. #define fi first
  6. #define se second
  7. #define maxb ((1<<8)+5)
  8. #define ll long long
  9. #define sti string
  10.  
  11. using namespace std;
  12.  
  13. const int mod=1e9+7;
  14. const int MAX=1e6;
  15.  
  16. int high[maxn],all[maxb],tmp[maxb];
  17. int cur[maxb],used[maxb];
  18. vector<int> adj[maxn];
  19. int ans[maxb],res[1000005];
  20. int dp[maxb][maxn];
  21. int choose[maxb],par[maxn];
  22. int up_cnt[maxn][maxb];
  23. int down_cnt[maxn][maxb];
  24. int a[maxn],q,n,order[maxn];
  25. int out[maxn];
  26. vector<pair<int,int>> que[maxn];
  27.  
  28. int SOSA[maxb][15],SOSB[maxb][15];
  29.  
  30. void SOS(int materialA[],int materialB[],int res[]){
  31.     for(int j=0;j<8;j++){
  32.         for(int mask=0;mask<(1<<8);mask++){
  33.             if(mask&(1<<j)){
  34.                 if(j==0) {
  35.                     SOSA[mask][j]=materialA[mask]+materialA[mask^(1<<j)];
  36.                     SOSB[mask][j]=materialB[mask]+materialB[mask^(1<<j)];
  37.                 }
  38.                 else {
  39.                     SOSA[mask][j]=SOSA[mask][j-1]+SOSA[mask^(1<<j)][j-1];
  40.                     SOSB[mask][j]=SOSB[mask][j-1]+SOSB[mask^(1<<j)][j-1];
  41.                 }
  42.             }
  43.             else{
  44.                 if(j==0) {
  45.                     SOSA[mask][j]=materialA[mask];
  46.                     SOSB[mask][j]=materialB[mask];
  47.                 }
  48.                 else {
  49.                     SOSA[mask][j]=SOSA[mask][j-1];
  50.                     SOSB[mask][j]=SOSB[mask][j-1];
  51.                 }
  52.             }
  53.         }
  54.     }
  55.     for(int mask=0;mask<(1<<8);mask++) choose[mask]=SOSA[mask][7]*SOSB[mask][7];
  56.     for(int j=0;j<8;j++){
  57.         for(int mask=0;mask<(1<<8);mask++){
  58.             if((mask&(1<<j))){
  59.                 if(j==0) dp[mask][j]=choose[mask]-choose[mask^(1<<j)];
  60.                 else dp[mask][j]=dp[mask][j-1] - dp[mask^(1<<j)][j-1];
  61.             }
  62.             else{
  63.                 if(j==0) dp[mask][j]=choose[mask];
  64.                 else dp[mask][j]=dp[mask][j-1];
  65.             }
  66.         }
  67.     }
  68.     for(int mask=0;mask<(1<<8);mask++) res[mask]=dp[mask][7];
  69. }
  70.  
  71. void dfs_pre(int u){
  72.    for(int v : adj[u]) {
  73.      par[v]=u;
  74.      high[v]=high[u]+1;
  75.      dfs_pre(v);
  76.    }
  77. }
  78.  
  79. signed main() {
  80.     itachi
  81.     cin>>n>>q;
  82.     for(int i=1;i<=n;i++) cin>>a[i];
  83.     for(int i=2;i<=n;i++){
  84.         int p; cin>>p;
  85.         adj[p].push_back(i);
  86.     }
  87.     dfs_pre(1);
  88.  
  89.     for(int id=1;id<=q;id++){
  90.         int x,i;
  91.         cin>>x>>i;
  92.         que[i].push_back({x,id});
  93.     }
  94.  
  95.     for(int i=1;i<=n;i++) order[i]=i;
  96.     sort(order+1,order+n+1,
  97.          [&](int a, int b){ return high[a] > high[b]; });
  98.     for(int i=1;i<=n;i++){
  99.         int u=order[i];
  100.         down_cnt[u][a[u]]++;
  101.         for(int v : adj[u]){
  102.             for(int mask=0;mask<(1<<8);mask++){
  103.                 down_cnt[u][mask | a[u]] += down_cnt[v][mask];
  104.             }
  105.         }
  106.     }
  107.  
  108.     for(int u=1;u<=n;u++){
  109.         memset(all,0,sizeof(all));
  110.         all[a[u]]++;
  111.         for(int mask=0;mask<(1<<8);mask++){
  112.             all[mask] += up_cnt[u][mask];
  113.         }
  114.  
  115.         for(int v : adj[u]){
  116.             memset(tmp,0,sizeof(tmp));
  117.             for(int mask=0;mask<(1<<8);mask++){
  118.                 tmp[mask | a[u]] += down_cnt[v][mask];
  119.             }
  120.             for(int mask=0;mask<(1<<8);mask++){
  121.                 all[mask] += tmp[mask];
  122.             }
  123.         }
  124.  
  125.         for(int v : adj[u]){
  126.             memset(tmp,0,sizeof(tmp));
  127.             for(int mask=0;mask<(1<<8);mask++){
  128.                 tmp[mask | a[u]] += down_cnt[v][mask];
  129.             }
  130.             for(int mask=0;mask<(1<<8);mask++){
  131.                 up_cnt[v][mask | a[v]] += all[mask] - tmp[mask];
  132.             }
  133.         }
  134.     }
  135.  
  136.     for(int i=1;i<=n;i++){
  137.         memset(out,0,sizeof(out));
  138.         memset(used,0,sizeof(used));
  139.         memset(ans,0,sizeof(ans));
  140.         used[a[i]]=1;
  141.         ans[a[i]]++;
  142.  
  143.         for(int mask=0;mask<(1<<8);mask++) cur[mask]=up_cnt[i][mask];
  144.         SOS(used, cur, out);
  145.         for(int mask=0;mask<(1<<8);mask++) ans[mask] += out[mask];
  146.         for(int mask=0;mask<(1<<8);mask++) used[mask] += cur[mask];
  147.  
  148.         for(int v : adj[i]){
  149.             memset(cur,0,sizeof(cur));
  150.             for(int mask=0;mask<(1<<8);mask++){
  151.                 cur[mask | a[i]] += down_cnt[v][mask];
  152.             }
  153.             SOS(used, cur, out);
  154.             for(int mask=0;mask<(1<<8);mask++) ans[mask] += out[mask];
  155.             for(int mask=0;mask<(1<<8);mask++) used[mask] += cur[mask];
  156.         }
  157.  
  158.         for(auto &it : que[i]){
  159.             int x = it.fi;
  160.             int id = it.se;
  161.             res[id] = ans[x];
  162.         }
  163.     }
  164.     for(int i=1;i<=q;i++) cout<<res[i]<<'\n';
  165.     return 0;
  166. }
  167.  
Success #stdin #stdout 0.01s 8060KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GpAgeq
language:
C++14 (gcc 8.3)
created:
2 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!