fork download
copy 
  1. #include<bits/stdc++.h>
  2. #pragma GCC optimize("O3,unroll-loops")
  3. #define int long long
  4. #define maxn 50005
  5. #define maxb 256
  6. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  7.  
  8. using namespace std;
  9.  
  10. int n,q;
  11. int a[maxn],par[maxn],high[maxn];
  12. vector<int> adj[maxn];
  13.  
  14. int up_cnt[maxn][maxb];
  15. int down_cnt[maxn][maxb];
  16.  
  17. int ans[maxn][maxb];
  18.  
  19. // SOS DP buffers
  20. int f[maxb][8], g[maxb][8], dp[maxb][8];
  21.  
  22. void OR_conv(int A[], int B[], int res[]){
  23.     for(int mask=0;mask<maxb;mask++){
  24.         f[mask][0]=A[mask];
  25.         g[mask][0]=B[mask];
  26.     }
  27.  
  28.     // SOS forward
  29.     for(int j=0;j<8;j++){
  30.         for(int mask=0;mask<maxb;mask++){
  31.             if(mask&(1<<j)){
  32.                 if(j){
  33.                     f[mask][j]=f[mask][j-1]+f[mask^(1<<j)][j-1];
  34.                     g[mask][j]=g[mask][j-1]+g[mask^(1<<j)][j-1];
  35.                 }else{
  36.                     f[mask][j]=A[mask]+A[mask^(1<<j)];
  37.                     g[mask][j]=B[mask]+B[mask^(1<<j)];
  38.                 }
  39.             }else{
  40.                 if(j){
  41.                     f[mask][j]=f[mask][j-1];
  42.                     g[mask][j]=g[mask][j-1];
  43.                 }else{
  44.                     f[mask][j]=A[mask];
  45.                     g[mask][j]=B[mask];
  46.                 }
  47.             }
  48.         }
  49.     }
  50.  
  51.     // multiply
  52.     for(int mask=0;mask<maxb;mask++){
  53.         dp[mask][0]=f[mask][7]*g[mask][7];
  54.     }
  55.  
  56.     // Möbius
  57.     for(int j=0;j<8;j++){
  58.         for(int mask=0;mask<maxb;mask++){
  59.             if(mask&(1<<j)){
  60.                 if(j==0) dp[mask][j]=dp[mask][0]-dp[mask^(1<<j)][0];
  61.                 else dp[mask][j]=dp[mask][j-1]-dp[mask^(1<<j)][j-1];
  62.             }else{
  63.                 if(j) dp[mask][j]=dp[mask][j-1];
  64.                 else dp[mask][j]=dp[mask][0];
  65.             }
  66.         }
  67.     }
  68.  
  69.     for(int mask=0;mask<maxb;mask++){
  70.         res[mask]=dp[mask][7];
  71.     }
  72. }
  73.  
  74. void dfs_pre(int u){
  75.     for(int v:adj[u]){
  76.         par[v]=u;
  77.         high[v]=high[u]+1;
  78.         dfs_pre(v);
  79.     }
  80. }
  81.  
  82. signed main(){
  83.     itachi
  84.  
  85.     cin>>n>>q;
  86.     for(int i=1;i<=n;i++) cin>>a[i];
  87.  
  88.     for(int i=2;i<=n;i++){
  89.         cin>>par[i];
  90.         adj[par[i]].push_back(i);
  91.     }
  92.  
  93.     dfs_pre(1);
  94.  
  95.     // ======================
  96.     // build up_cnt
  97.     // ======================
  98.     static int order[maxn];
  99.     for(int i=1;i<=n;i++) order[i]=i;
  100.  
  101.     sort(order+1,order+n+1,[](int u,int v){
  102.         return high[u]<high[v];
  103.     });
  104.  
  105.     for(int i=1;i<=n;i++){
  106.         int u=order[i];
  107.         up_cnt[u][a[u]]++;
  108.  
  109.         for(int mask=0;mask<maxb;mask++){
  110.             up_cnt[u][mask | a[u]] += up_cnt[par[u]][mask];
  111.         }
  112.     }
  113.  
  114.     // ======================
  115.     // build down_cnt
  116.     // ======================
  117.     sort(order+1,order+n+1,[](int u,int v){
  118.         return high[u]>high[v];
  119.     });
  120.  
  121.     for(int i=1;i<=n;i++){
  122.         int u=order[i];
  123.         down_cnt[u][a[u]]++;
  124.  
  125.         for(int v:adj[u]){
  126.             for(int mask=0;mask<maxb;mask++){
  127.                 down_cnt[u][mask | a[u]] += down_cnt[v][mask];
  128.             }
  129.         }
  130.     }
  131.  
  132.     // ======================
  133.     // xử lý từng node
  134.     // ======================
  135.     static int used[maxb], group[maxb], tmp[maxb];
  136.  
  137.     for(int i=1;i<=n;i++){
  138.  
  139.         for(int mask=0;mask<maxb;mask++){
  140.             used[mask]=0;
  141.             ans[i][mask]=0;
  142.         }
  143.  
  144.         // ===== group 1: node i =====
  145.         for(int mask=0;mask<maxb;mask++) group[mask]=0;
  146.         group[a[i]] = 1;
  147.  
  148.         OR_conv(used, group, tmp);
  149.         for(int mask=0;mask<maxb;mask++) ans[i][mask]+=tmp[mask];
  150.         for(int mask=0;mask<maxb;mask++) used[mask]+=group[mask];
  151.  
  152.         // ===== group 2: ancestor =====
  153.         for(int mask=0;mask<maxb;mask++) group[mask]=up_cnt[i][mask];
  154.  
  155.         OR_conv(used, group, tmp);
  156.         for(int mask=0;mask<maxb;mask++) ans[i][mask]+=tmp[mask];
  157.         for(int mask=0;mask<maxb;mask++) used[mask]+=group[mask];
  158.  
  159.         // ===== group 3: từng subtree =====
  160.         for(int v:adj[i]){
  161.             for(int mask=0;mask<maxb;mask++) group[mask]=0;
  162.  
  163.             for(int mask=0;mask<maxb;mask++){
  164.                 group[mask | a[i]] += down_cnt[v][mask];
  165.             }
  166.  
  167.             OR_conv(used, group, tmp);
  168.  
  169.             for(int mask=0;mask<maxb;mask++) ans[i][mask]+=tmp[mask];
  170.             for(int mask=0;mask<maxb;mask++) used[mask]+=group[mask];
  171.         }
  172.     }
  173.  
  174.     while(q--){
  175.         int x,i;
  176.         cin>>x>>i;
  177.         cout<<ans[i][x]<<'\n';
  178.     }
  179. }
Success #stdin #stdout 0.01s 7512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xDw5wA
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!