fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std ;
  4. #define ll long long
  5. #define str string
  6. #define fir first
  7. #define sec second
  8. #define FOR(i,a,b) for (int i = (a) ; i <= (b) ; i++)
  9. #define FORD(i,a,b) for (int i = (a) ; i >= (b) ; i--)
  10. #define ALL(x) (x).begin() , (x).end()
  11. #define pb push_back
  12. const int maxn = 1e5 ;
  13.  
  14. int a[maxn + 3 ] ;  
  15. int n , q ;
  16. vector < int > G[maxn + 3 ] ;
  17. void dfs (int u , int par , int x ) {
  18.     a[u] ^= x ;
  19. //    cout << "u" << u << ' ' << a[u] << ' '<< x << '\n';
  20.     for (auto v : G[u]){
  21.         if ( v == par ) continue ;
  22.         dfs ( v , u , x ) ;
  23.     }
  24. }
  25. int Par[maxn + 3] ;
  26. bool vt[maxn +3 ] ;
  27. void dfs_tim_cha( int u , int par ) {
  28.     Par[u] = par ;
  29.     for (auto v : G[u]){
  30.         if ( v == par ) continue ;
  31.         dfs_tim_cha ( v , u ) ;
  32.     }
  33. }
  34. int get_bfs (int st , int x ){
  35.     FOR ( i , 1 , n ) vt[i] = 0 ;
  36.     int ans = 0 ;
  37.     queue < pair < int , int >  > q ;
  38.     q.push ( { a[st] , st }) ;
  39.     vt[st] = 1 ;
  40. //    for (int i = 1 ; i <= n ; i ++ ) cout << a[i] << ' ' ;
  41. //    cout << '\n' ;
  42.     while ( q.size()){
  43.         auto [ du , u ] = q.front() ;
  44.         q.pop() ;
  45.  
  46.         if ( u == x ) {
  47.             return du ;
  48.  
  49.         }
  50.         for (auto v : G[u]){
  51.             if ( !vt[v]){
  52.                 vt[v] = 1 ;
  53.                 int new_du = du ^ a[v] ;
  54.                 q.push ( { new_du , v }) ;
  55.             }
  56.         }
  57.     }
  58. }
  59. #define name "XORTREE"
  60. void sub1(){
  61.     dfs_tim_cha(1 , 1 ) ;
  62.     while ( q -- ){
  63.         int pl , u , v ; cin >> pl >> u >> v ;
  64.         if ( pl == 1 ) {
  65.             dfs ( u , Par[u] , v ) ;
  66.         }
  67.         else cout << get_bfs ( u , v ) << '\n' ;
  68.     }
  69. }
  70. int in[maxn + 3 ] , ou[maxn + 3 ] ;
  71. int cnt = 1 ;
  72. const int LOG = 18 ;
  73. int up[maxn + 3 ] [LOG + 3 ] ;
  74. int lazy[maxn * 8 + 3 ] ;
  75. int s[maxn * 8 + 3 ] ;
  76. void fix (int id ,int l , int r ) {
  77.     if ( ( r - l + 1 ) & 1 ) s[id] ^= lazy[id] ;
  78.  
  79.     if ( l != r ) {
  80.         lazy[id * 2 + 1 ] ^= lazy[id] ;
  81.         lazy[id * 2 ] ^= lazy[id] ;
  82.     }
  83.     lazy[id] = 0 ;
  84. }
  85. void update ( int id , int l , int r , int u , int v , int val ){
  86.     fix ( id , l , r ) ;
  87.     if ( u > r || l > v ) return  ;
  88.     if ( u <= l && r <= v ) {
  89.         lazy[id] = val ;
  90.         fix ( id , l , r ) ;
  91.         return ;
  92.     }
  93.     int m = ( l + r ) >> 1ll ;
  94.     update( id * 2 , l , m , u , v , val ) ;
  95.     update( id * 2 + 1 , m + 1 , r , u , v , val ) ;
  96.     s[id] = s[id *2 ] ^ s[id * 2 + 1] ;
  97. }
  98. int get ( int id , int l , int r , int u , int v ){
  99. //    fix ( id , l , r ) ;
  100.     if ( u > r || l > v ) return 0;
  101.     fix ( id , l , r ) ;
  102.     if ( u <= l && r <= v ) {
  103.         return s[id] ;
  104. //        return ;
  105.     }
  106.     int m = ( l + r ) >> 1ll ;
  107.     int one = get ( id * 2 , l , m , u , v ) ;
  108.     int two = get ( id * 2 + 1 , m + 1  , r , u , v ) ;
  109.     return one ^ two ;
  110. }
  111. int h[maxn + 3 ] ;
  112. void dfs_sub2 (int u , int par ) {
  113.     in[u] = cnt ++ ;
  114.     for (auto v : G[u]){
  115.         if ( v == par ) continue ;
  116.         h[v] = h[u] + 1 ;
  117.         up[v][0] = u ;
  118.         for (int i = 1 ; i <= LOG ; i ++ ) {
  119.             up[v][i] = up[up[v][i-1]][i-1] ;
  120.         }
  121.         dfs_sub2( v , u ) ;
  122.     }
  123.     ou[u] = cnt ++ ;
  124. }
  125. int lca (int u , int v ) {
  126.     if ( h[u] < h[v] ) swap ( u , v ) ;
  127.     int k = h[u] - h[v] ;
  128.     for (int i = 0 ; ( 1 << i ) <= k ; i ++ ) {
  129.         if ( ( k >> i ) & 1 ) u = up[u][i] ;
  130.     }
  131.     if ( u == v ) return u ;
  132.     for ( int i = LOG ; i >= 0 ; i-- ) {
  133.  
  134.         if (up[u][i] != up[v][i]) {
  135.             u = up[u][i] ;
  136.             v = up[v][i] ;
  137.         }
  138.     }
  139.     return up[u][0] ;
  140. }
  141. void sub2() {
  142.     dfs_sub2( 1 , 1 ) ;
  143.  
  144.     FOR ( u , 1 , n ) {
  145.         int random_c = 0 ;
  146.         update ( 1 , 1 , cnt , in[u] , in[u] , a[u] ) ;
  147.         update ( 1 , 1 , cnt , ou[u] , ou[u] , a[u] ) ;
  148.     }
  149.     while ( q -- ) {
  150.         int pl , u , v ; cin >> pl >> u >> v ;
  151.         if ( pl == 1 ) {
  152.             update ( 1 , 1 , cnt , in[u] , ou[u] , v ) ;
  153.         }
  154.         else {
  155.             int lcaa = lca ( u , v ) ;
  156.             if ( lcaa == u ){
  157.                 cout << (get ( 1 , 1 , cnt , in[u] , in[v] )) << '\n' ;
  158.                 continue ;
  159.             }
  160.             cout << (get ( 1 , 1 , cnt , in[lcaa] , in[u] ) ^ get ( 1 , 1 , cnt , in[lcaa] , in[v] ) ^ get ( 1 , 1 , cnt , in[lcaa] , in[lcaa] )) << '\n' ;
  161.  
  162.         }
  163.     }
  164. }
  165. int main(){
  166.  
  167.     ios_base::sync_with_stdio(0) ;
  168.     cin.tie(0) ; cout.tie(0) ;
  169.     if(fopen(name".inp" , "r")){
  170.         freopen(name".inp" , "r" , stdin ) ;
  171.         freopen(name".out" , "w" , stdout ) ;
  172.     }
  173.     cin >> n >> q ;
  174.  
  175.     FOR ( i , 1 , n ) cin >> a[i] ;
  176.     FOR ( i , 2 , n ) {
  177.         int u , v ; cin >> u >> v ;
  178.         G[u].pb ( v ) ;
  179.         G[v].pb ( u ) ;
  180.     }
  181.     sub2() ;
  182. }
  183.  
Success #stdin #stdout 0.01s 8880KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/3n2Z0l
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!