fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define double long double
  4. #define endl "\n"
  5. #define fi first
  6. #define se second
  7. #define MASK(i) (1LL << (i))
  8. #define BIT(x, i) (((x) >> (i)) & 1)
  9. #define creby_ThienNhan return 0;
  10. #define TKimorz ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  11. using namespace std;
  12. const int LimN=2e5+5;
  13. const int N=1e5+5;
  14. const int M=1e3+5;
  15. const int BASE=256;
  16. const int mod=1e9+7;
  17. char d4c[4]={'R','D','L','U'};
  18. ll d4x[4]={0,1,0,-1};
  19. ll d4y[4]={1,0,-1,0};
  20. ll d4x_tuong[4]={-2,-2,2,2};
  21. ll d4y_tuong[4]={-2,2,-2,2};
  22. ll d8x[8]={0,1,-1,0,-1,1,1,-1};
  23. ll d8y[8]={1,0,0,-1,-1,1,-1,1};
  24. ll d8x_ma[8]={-1,-1,+1,+1,-2,-2,+2,+2};
  25. ll d8y_ma[8]={-2,+2,-2,+2,-1,+1,-1,+1};
  26. template<class X, class Y>
  27. bool maximize(X& x, const Y y) {
  28.     if (y > x) {x = y; return true;}
  29.     return false;
  30. }
  31. template<class X, class Y>
  32. bool minimize(X& x, const Y y) {
  33.     if (y < x) {x = y; return true;}
  34.     return false;
  35. }
  36. ll pow(ll a,ll b,ll c){
  37.     ll tich = 1;
  38.     a = a % c;
  39.     for (; b > 0; b >>= 1 , a = a * a % c){
  40.         if (b & 1) tich = tich * a % c;
  41.       }
  42.     return tich;
  43. }
  44. ll n, q, cnt;
  45. ll a[LimN];
  46. ll head[LimN], p[LimN], heavy[LimN], h[LimN], pos[LimN],invpos[LimN];
  47. vector<int> adj[LimN];
  48. struct tn{
  49.     int cnt[10];
  50.     int lazy;
  51.     tn() {
  52.         memset(cnt,0,sizeof cnt);
  53.         lazy=0;
  54.     }
  55. }st[LimN * 4];
  56. int dfs(int u, int par) {
  57.     int cur_sz = 1, max_son_sz = 0;
  58.     for (int v : adj[u]) {
  59.         if (v == par) continue;
  60.         h[v] = h[u] + 1;
  61.         p[v] = u;
  62.         int son_sz = dfs(v, u);
  63.         if (son_sz > max_son_sz) {
  64.             max_son_sz = son_sz;
  65.             heavy[u] = v;
  66.         }
  67.         cur_sz += son_sz;
  68.     }
  69.     return cur_sz;
  70. }
  71.  
  72. void hld(int u, int top) {
  73.     head[u] = top;
  74.     pos[u] = ++cnt;
  75.     invpos[cnt]=u;
  76.     if (heavy[u]) hld(heavy[u], top);
  77.     for (int v : adj[u]) {
  78.         if (v != p[u] && v != heavy[u]) {
  79.             hld(v, v);
  80.         }
  81.     }
  82. }
  83.  
  84. void down(int id, int l, int r, int mask) {
  85.     int len=r-l+1;
  86.     for (int i=0; i<10; i++) {
  87.         if (BIT(mask,i)) {
  88.             st[id].cnt[i]=len-st[id].cnt[i];
  89.         }
  90.     }
  91.     st[id].lazy^=mask;
  92. }
  93. void push(int id, int l, int r) {
  94.     if (st[id].lazy) {
  95.         int mid=(l+r)/2;
  96.         down(id*2,l,mid,st[id].lazy);
  97.         down(id*2+1,mid+1,r,st[id].lazy);
  98.         st[id].lazy=0;
  99.     }
  100. }
  101. void build(int id, int l, int r) {
  102.     if (l==r) {
  103.         int val=a[invpos[l]];
  104.         for (int i=0; i<10; i++) {
  105.             st[id].cnt[i]= val >> i & 1;
  106.         }
  107.         return;
  108.     }
  109.     int mid=(l+r)/2;
  110.     build(id*2,l,mid);
  111.     build(id*2+1,mid+1,r);
  112.     for (int i=0; i<10; i++) {
  113.         st[id].cnt[i]=st[id*2].cnt[i] + st[id*2+1].cnt[i];
  114.     }
  115. }
  116.  
  117. void update(int id, int l, int r, int u, int v, int val) {
  118.     if (r < u || v < l) return;
  119.     if (u <= l && r <= v) {
  120.         down(id,l,r,val);
  121.         return;
  122.     }
  123.     push(id,l,r);
  124.     int mid = (l + r) / 2;
  125.     update(id * 2, l, mid, u, v, val);
  126.     update(id * 2 + 1, mid + 1, r, u, v, val);
  127.     for (int i=0; i<10; i++) {
  128.         st[id].cnt[i]=st[id*2].cnt[i] + st[id*2+1].cnt[i];
  129.     }
  130. }
  131.  
  132. ll get(int id, int l, int r, int u, int v) {
  133.     if (r < u || l > v) return 0;
  134.     if (u <= l && r <= v) {
  135.         int ans=0;
  136.         for (int i=0; i<10; i++) {
  137.             ans+=st[id].cnt[i] * MASK(i);
  138.         }
  139.         return ans;
  140.     }
  141.     push(id,l,r);
  142.     int mid = l + r >> 1;
  143.     return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
  144. }
  145.  
  146. void update_path(int x, int y, int val) {
  147.     while (head[x] != head[y]) {
  148.         if (h[head[x]] < h[head[y]]) swap(x, y);
  149.         update(1, 1, n, pos[head[x]], pos[x], val);
  150.         x = p[head[x]];
  151.     }
  152.     if (h[x] > h[y]) swap(x, y);
  153.     update(1, 1, n, pos[x], pos[y], val);
  154. }
  155.  
  156. ll query(int x, int y) {
  157.     ll res = 0;
  158.     while (head[x] != head[y]) {
  159.         if (h[head[x]] < h[head[y]]) swap(x, y);
  160.         res += get(1, 1, n, pos[head[x]], pos[x]);
  161.         x = p[head[x]];
  162.     }
  163.     if (h[x] > h[y]) swap(x, y);
  164.     res += get(1, 1, n, pos[x], pos[y]);
  165.     return res;
  166. }
  167.  
  168.  
  169. void solve() {
  170.     int sub;
  171.     cin >> sub;
  172.     cin >> n;
  173.     for (int i = 1; i <= n; ++i) cin >> a[i];
  174.     for (int i = 1; i < n; ++i) {
  175.         int u, v; cin >> u >> v;
  176.         adj[u].push_back(v);
  177.         adj[v].push_back(u);
  178.     }
  179.     dfs(1, 0);
  180.     hld(1, 1);
  181.     build(1,1,n);
  182.     cin >> q;
  183.     while (q--) {
  184.         int type; cin >> type;
  185.         if (type == 1) {
  186.             int x, y, v;
  187.             cin >> x >> y >> v;
  188.             update_path(x, y, v);
  189.         } else {
  190.             int x, y;
  191.             cin >> x >> y;
  192.             cout << query(x, y) << endl;
  193.         }
  194.     }
  195. }
  196.  
  197. int main() {
  198.     TKimorz
  199.     ll t=1;
  200.     while (t--) {
  201.         solve();
  202.     }
  203.     creby_ThienNhan
  204. }
  205.  
Success #stdin #stdout 0.02s 50812KB
comments (?)
stdin
copy 
1
6
4 3 2 5 3 4
1 2
1 3
2 4
2 5
3 6
2
1 2 4 2
2 1 2
stdout
copy 
5
https://ideone.com/Sbirwk
language:
C++14 (gcc 8.3)
created:
8 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!