fork download
copy 
  1. #include <bits/stdc++.h>
  2. //#define int long long
  3. #define double long double
  4. #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  5. #define pb push_back
  6. #define ALL(i) i.begin(),i.end()
  7. #define gcd(i,j) __gcd(i,j)
  8. #define fi first
  9. #define se second
  10. #define bitCount(i) __builtin_popcount(i)
  11. //#define X first
  12. //#define Y second
  13. #define eps 0.00000001
  14. #define ist insert
  15. //#define mul(a,b,c) (a%c)*(b%c)%c
  16. // #pragma GCC optimize("Ofast","inline","-ffast-math")
  17. // #pragma GCC optimize("O3")
  18. // #pragma GCC target("avx,sse2,sse3,sse4,mmx")
  19. int max(int x,int y){return x>=y?x:y;}
  20. int min(int x,int y){return x>=y?y:x;}
  21. using namespace std;
  22. typedef long long ll;
  23. const int N=100005;
  24. const int M=505;
  25. const int MOD=998244353;//1000000007;
  26. const ll INF=9223372036854775807;//2147483647;
  27. const double PI=acos(-1);
  28. typedef pair<int,int> pii;
  29. typedef pair<double,double> pdd;
  30. typedef pair<double,int> pdi;
  31.  
  32. struct Trie{
  33.     int tot;
  34.     vector<int> trie[2];
  35.     vector<int> cnt;
  36.     void init(int _n){
  37.         trie[0].resize(N*100);
  38.         trie[1].resize(N*100);
  39.         cnt.resize(N*100);
  40.         tot=1;
  41.     }
  42.     void add(int x){
  43.         int cur=1;
  44.         for (int i=30;i>=0;i--){
  45.             int idx=((1<<i)&x)!=0;
  46.             if (trie[idx][cur]==0) trie[idx][cur]=++tot;
  47.             cur=trie[idx][cur];
  48.             cnt[cur]++;
  49.             // assert(tot<N*100);
  50.         }    
  51.     }
  52.     void del(int x){
  53.         int cur=1;
  54.         for (int i=30;i>=0;i--){
  55.             int idx=((1<<i)&x)!=0;
  56.             if (trie[idx][cur]==0) trie[idx][cur]=++tot;
  57.             cur=trie[idx][cur];
  58.             cnt[cur]--;
  59.         }
  60.         // assert(tot<N*100);
  61.     }
  62.     int que(int x){
  63.         int res=0, cur=1;
  64.         for (int i=30;i>=0;i--){
  65.             int idx=((1<<i)&x)!=0;
  66.             if (trie[!idx][cur]!=0&&cnt[trie[!idx][cur]]!=0) {
  67.                 res|=(1<<i);
  68.                 cur=trie[!idx][cur];
  69.             }
  70.             else cur=trie[idx][cur];
  71.         }
  72.         return res;
  73.     }
  74. };
  75.  
  76. int n,K;
  77. int c[N], a[N];
  78. vector<int> e[N];
  79. int hson[N], sz[N];
  80. int clr[N];
  81. int cnt[N*32]{};
  82. int ans[N];
  83. Trie subtree, root;
  84. void dfs1(int v,int pre){
  85.     int mx=0,son=0; 
  86.     for (int i:e[v]) if (i!=pre){
  87.         dfs1(i,v);
  88.         if (sz[i]>mx){
  89.             mx=sz[i];
  90.             son=i;
  91.         }
  92.         sz[v]+=sz[i];
  93.     }
  94.     hson[v]=son;
  95.     sz[v]++;
  96. }
  97. void add(int v){
  98.     root.del(clr[c[v]]);
  99.     clr[c[v]]^=a[v];
  100.     root.add(clr[c[v]]);
  101.     subtree.add(a[v]);
  102. }
  103. void del(int v){
  104.     root.del(clr[c[v]]);
  105.     clr[c[v]]^=a[v];
  106.     root.add(clr[c[v]]);
  107.     subtree.del(a[v]);
  108. }
  109. void DDel(int v,int pre){
  110.     for (int i:e[v]) if (i!=pre) DDel(i,v);
  111.     del(v);
  112. }
  113. void AAdd(int v,int pre){
  114.     for (int i:e[v]) if (i!=pre) AAdd(i,v);
  115.     add(v);
  116. }
  117. void calc(int v,int pre){
  118.     for (int i:e[v]) if (i!=pre && i!=hson[v]){
  119.         calc(i, v);
  120.         DDel(i,v);
  121.     }
  122.     if (hson[v]!=0) calc(hson[v], v);
  123.     for (int i:e[v]) if (i!=pre && i!=hson[v]){
  124.         AAdd(i,v);
  125.     } 
  126.     int ans1=subtree.que(clr[c[v]]^a[v]);
  127.     int ans2=root.que(a[v]);
  128.  
  129.     add(v);
  130.     if (K==1) ans[v]=max(ans1, ans2);
  131.     else ans[v]=clr[c[v]];
  132. }
  133. void sol(){
  134.     cin >>n>>K;
  135.     for (int i=1;i<=n;i++) cin >>c[i];
  136.     for (int i=1;i<=n;i++) cin >>a[i];
  137.  
  138.     for (int i=1,x,y;i<n;i++){
  139.         cin >>x>>y;
  140.         e[x].pb(y);
  141.         e[y].pb(x);
  142.     }
  143.     subtree.init(n); subtree.add(0);
  144.     root.init(n); for (int i=1;i<=n;i++) root.add(0);
  145.     dfs1(1,0);
  146.     calc(1,0);
  147.     for (int i=1;i<=n;i++) cout <<ans[i]<<" \n"[i==n];
  148. }  
  149.  
  150. signed main(){
  151.     IOS
  152.     //srand(time(NULL));
  153.     int _=1;    
  154.     // cin >>_;
  155.     while (_--) sol();
  156.     return 0;
  157. }
  158.  
  159.  
Success #stdin #stdout 0.05s 242524KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4hdZxr
language:
C++14 (gcc 8.3)
created:
16 hours 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!