fork download
copy 
  1. #include<bits/stdc++.h>
  2. #pragma GCC optimize("O3,unroll-loops")
  3. #define int long long
  4. #define ll long long
  5. #define maxn 2000005
  6. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  7. #define fi first
  8. #define sti string
  9. #define se second
  10.  
  11. using namespace std;
  12.  
  13. vector<int> adj[maxn];
  14. int sz[maxn],heavy[maxn];
  15. int n,q,Timer=0,node[maxn];
  16. int In[maxn],Out[maxn];
  17. set<int> S;
  18. int ans[maxn],a[maxn],res=0;
  19. int prexor[maxn];
  20. bool bad[maxn];
  21.  
  22. void dfs(int u,int p){
  23.     sz[u]=1;
  24.     int Max=0;
  25.     In[u]=++Timer;
  26.     node[Timer]=u;
  27.  
  28.     for(int v : adj[u]){
  29.         if(v==p) continue;
  30.         prexor[v]=prexor[u]^a[v];
  31.         dfs(v,u);
  32.         sz[u]+=sz[v];
  33.         if(sz[v] > Max){
  34.             Max=sz[v];
  35.             heavy[u]=v;
  36.         }
  37.     }
  38.  
  39.     Out[u]=Timer;
  40. }
  41.  
  42. void add(int u){
  43.     S.insert(prexor[u]);
  44. }
  45.  
  46. void sub(int u){
  47.     auto it = S.find(prexor[u]);
  48.     if(it != S.end()) S.erase(it);
  49. }
  50.  
  51. void sack(int u,int p,bool keep){
  52.  
  53.    for(int v : adj[u]){
  54.       if(v==p || v==heavy[u]) continue;
  55.       sack(v,u,0);
  56.    }
  57.  
  58.    if(heavy[u]) sack(heavy[u],u,1);
  59.  
  60.    bool found=0;
  61.  
  62.    for(int v : adj[u]){
  63.       if(v==p || v==heavy[u]) continue;
  64.       for(int pos=In[v];pos<=Out[v];pos++){
  65.           int x = node[pos];
  66.           if(bad[x]){
  67.              pos=Out[x];
  68.              continue;
  69.           }
  70.           if(S.count(prexor[x] ^ a[u])){
  71.              found=1;
  72.              break;
  73.           }
  74.       }
  75.       if(found) break;
  76.       for(int pos=In[v];pos<=Out[v];pos++){
  77.           int x = node[pos];
  78.           if(bad[x]){
  79.               pos = Out[x];
  80.               continue;
  81.           }
  82.           add(x);
  83.       }
  84.    }
  85.  
  86.    if(S.count(prexor[u] ^ a[u])) found=1;
  87.  
  88.    if(found){
  89.       res++;
  90.       bad[u]=1;
  91.       S.clear();
  92.       return ;
  93.    }
  94.  
  95.    add(u);
  96.  
  97.    if(!keep){
  98.      for(int pos=In[u];pos<=Out[u];pos++){
  99.         sub(node[pos]);
  100.      }
  101.    }
  102. }
  103.  
  104. signed main() {
  105.     itachi
  106.  
  107.     cin>>n;
  108.     for(int i=1;i<=n;i++) cin>>a[i];
  109.  
  110.     for(int i=2;i<=n;i++){
  111.         int u,v;
  112.         cin>>u>>v;
  113.         adj[u].push_back(v);
  114.         adj[v].push_back(u);
  115.     }
  116.  
  117.     prexor[1]=a[1];
  118.  
  119.     dfs(1,0);
  120.     sack(1,0,1);
  121.     cout<<res;
  122.     return 0;
  123. }
  124.  
Success #stdin #stdout 0.02s 62596KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Pkc3pA
language:
C++14 (gcc 8.3)
created:
1 day 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!