fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define pii pair<int, int>
  4. #define ALL(v) (v).begin(), v.end()
  5. using namespace std;
  6. const int maxn = 1e6 + 5;
  7. const int mod = 1e9 + 7;
  8. const int oo = 1e18;
  9. const int logg = 19;
  10. const int base = 31;
  11. int n, a[maxn], pre[maxn], ans = 0;
  12. set<int> S[maxn];
  13. vector<int> adj[maxn];
  14. void dfs(int u, int p){
  15.     pre[u] = pre[p] ^ a[u];
  16.     S[u].insert(pre[u]);
  17.     bool del = false;
  18.     for(int v : adj[u]){
  19.         if(v == p) continue;
  20.         dfs(v, u);
  21.         if(del) continue;
  22.         bool check = false;
  23.         if(S[u].size() < S[v].size()){
  24.             for(int x : S[u]){
  25.                 if(S[v].count(x ^ a[u])){
  26.                     del = true;
  27.                     break;
  28.                 }
  29.             }
  30.         }
  31.         else{
  32.             for(int x : S[v]){
  33.                 if(S[u].count(x ^ a[u])){
  34.                     check = true;
  35.                     break;
  36.                 }
  37.             }
  38.         }
  39.         if(check){
  40.             del = true;
  41.         }
  42.         else{
  43.             if(S[u].size() < S[v].size()){
  44.                 S[u].swap(S[v]);
  45.             }
  46.             for(int x : S[v]){
  47.                 S[u].insert(x);
  48.             }
  49.         }
  50.     }
  51.     if(del){
  52.         ans++;
  53.         S[u].clear();
  54.     }
  55. }
  56. signed main(){
  57. 	ios_base::sync_with_stdio(0);
  58. 	cin.tie(0);
  59. 	cout.tie(0);
  60. 	//freopen("dincpath.inp", "r", stdin);
  61. 	//freopen("dincpath.out", "w", stdout);
  62. 	cin >> n;
  63. 	for(int i = 1; i <= n; i++){
  64.         cin >> a[i];
  65. 	}
  66. 	for(int i = 1; i < n; i++){
  67.         int u, v;
  68.         cin >> u >> v;
  69.         adj[u].push_back(v);
  70.         adj[v].push_back(u);
  71. 	}
  72.     dfs(1, 0);
  73.     cout << ans;
  74. 	return 0;
  75. }
  76.  
Success #stdin #stdout 0.02s 74920KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/aN4dDy
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!