fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. int n;
  5. vector<int> a, flat;
  6. vector<vector<int>> adj;
  7.  
  8. struct LCA
  9. {
  10.     vector<vector<int>> par;
  11.     const int lg = 18;
  12.     vector<int> dist; // distance from the root
  13.     vector<int> in, out;
  14.     int t = 0;
  15.     LCA(int n)
  16.     {
  17.         in = out = dist = vector<int>(n + 4);
  18.         par = vector<vector<int>>(n + 4, vector<int>(lg + 5));
  19.         dist[1] = 0;
  20.         dfs(1, 1);
  21.         pre(n);
  22.     }
  23.     void dfs(int i, int p)
  24.     {
  25.         dist[i] = dist[p] + (i != 1);
  26.         flat.push_back(i);
  27.         in[i] = t++;
  28.         par[i][0] = p;
  29.         for (auto j : adj[i])
  30.         {
  31.             if (j != p)
  32.                 dfs(j, i);
  33.         }
  34.         flat.push_back(i);
  35.         out[i] = t++;
  36.     }
  37.     bool isparent(int v, int p)
  38.     { // is p parent of v
  39.         return in[p] <= in[v] and out[p] >= out[v];
  40.     }
  41.     void pre(int n)
  42.     {
  43.         for (int i = 1; i < lg; i++)
  44.         {
  45.             for (int f = 1; f <= n; f++)
  46.             {
  47.                 par[f][i] = par[par[f][i - 1]][i - 1];
  48.             }
  49.         }
  50.     }
  51.  
  52.     int lca(int a, int b)
  53.     {
  54.         if (isparent(a, b))
  55.             return b;
  56.         if (isparent(b, a))
  57.             return a;
  58.         int ret = a;
  59.         for (int i = lg - 1; ~i; i--)
  60.         {
  61.             if (!isparent(b, par[ret][i]))
  62.                 ret = par[ret][i];
  63.         }
  64.         return par[ret][0];
  65.     }
  66.     int getdist(int u, int p)
  67.     { // how many nodes are there int path from u to p
  68.         return dist[u] - dist[p] + 1;
  69.     }
  70. };
  71. vector<int> in, out;
  72.  
  73. struct Node
  74. {
  75.     int frq[31]{};
  76. };
  77.  
  78. struct Segtree
  79. {
  80.     vector<Node> tree;
  81.     Node neutral = Node();
  82.     Segtree(int n, vector<int> &v)
  83.     {
  84.         int sz = 1;
  85.         while (sz <= n)
  86.         {
  87.             sz *= 2;
  88.         }
  89.         tree.resize(sz * 2);
  90.         build(1, 0, n - 1, v);
  91.     }
  92.     Node Single(int data)
  93.     {
  94.         Node ret;
  95.         int g = abs(data);
  96.         for (int i = 0; i < 31; i++)
  97.         {
  98.             ret.frq[i] = (data < 0 ? -1 : 1) * ((g & (1ll << i)) > 0);
  99.         }
  100.         return ret;
  101.     }
  102.     Node Merge(Node a, Node b)
  103.     {
  104.         Node ret;
  105.         for (int i = 0; i < 31; i++)
  106.         {
  107.             ret.frq[i] = a.frq[i] + b.frq[i];
  108.         }
  109.         return ret;
  110.     }
  111.     void build(int x, int lx, int rx, const vector<int> &v)
  112.     {
  113.         if (lx == rx)
  114.             return tree[x] = Single(v[lx]), void();
  115.         int m = (lx + rx) >> 1;
  116.         build(x * 2, lx, m, v);
  117.         build(x * 2 + 1, m + 1, rx, v);
  118.         tree[x] = Merge(tree[x * 2], tree[x * 2 + 1]);
  119.     }
  120.     void change(int x, int lx, int rx, const int &i, const int &val)
  121.     {
  122.         if (lx == rx)
  123.             return tree[x] = Single(val), void();
  124.         int m = (lx + rx) >> 1;
  125.         if (i <= m)
  126.             change(x * 2, lx, m, i, val);
  127.         else
  128.             change(x * 2 + 1, m + 1, rx, i, val);
  129.         tree[x] = Merge(tree[x * 2], tree[x * 2 + 1]);
  130.     }
  131.     Node query(int x, int lx, int rx, const int &l, const int &r)
  132.     {
  133.         if (lx > r or rx < l)
  134.             return neutral;
  135.         if (lx >= l and rx <= r)
  136.             return tree[x];
  137.         int m = (lx + rx) >> 1;
  138.         return Merge(query(x * 2, lx, m, l, r), query(x * 2 + 1, m + 1, rx, l, r));
  139.     }
  140. };
  141. int main()
  142. {
  143.     ios_base::sync_with_stdio(0);
  144.     cin.tie(0);
  145.     cout.tie(0);
  146.     cin >> n;
  147.     a = vector<int>(n + 4);
  148.     for (int i = 1; i <= n; i++)
  149.     {
  150.         cin >> a[i];
  151.     }
  152.     adj = vector<vector<int>>(n + 4);
  153.     for (int i = 0; i < n - 1; i++)
  154.     {
  155.         int u, v;
  156.         cin >> u >> v;
  157.         adj[u].push_back(v);
  158.         adj[v].push_back(u);
  159.     }
  160.     LCA lca(n);
  161.     in = lca.in;
  162.     out = lca.out;
  163.     vector<int> tmp(flat.size());
  164.     bool vis[n + 4]{};
  165.     for (int i = 0; i < flat.size(); i++)
  166.     {
  167.         tmp[i] = ((vis[flat[i]] ? -a[flat[i]] : a[flat[i]]));
  168.         vis[flat[i]] = true;
  169.     }
  170.     Segtree tree(flat.size(), tmp);
  171.     int q;
  172.     cin >> q;
  173.     while (q--)
  174.     {
  175.         int op;
  176.         cin >> op;
  177.         if (op == 1)
  178.         {
  179.             int u, v;
  180.             cin >> u >> v;
  181.             int lc = lca.lca(u, v);
  182.             auto resu = tree.query(1, 0, flat.size() - 1, in[lc], in[u]).frq;
  183.             auto resv = tree.query(1, 0, flat.size() - 1, in[lc], in[v]).frq;
  184.             int tot = lca.getdist(u, lc) + lca.getdist(v, lc) - 1;
  185.             ll ans = 0;
  186.             for (int i = 0; i < 31; i++)
  187.             {
  188.                 if (resu[i] + resv[i] - ((a[lc] & (1ll << i)) > 0) == tot)
  189.                     ans += (1ll << i);
  190.             }
  191.             cout << ans << '\n';
  192.         }
  193.         else
  194.         {
  195.             int u, x;
  196.             cin >> u >> x;
  197.             a[u] = x;
  198.             tree.change(1, 0, flat.size() - 1, in[u], x);
  199.             tree.change(1, 0, flat.size() - 1, out[u], -x);
  200.         }
  201.     }
  202. }
  203.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GitbXP
language:
C++14 (gcc 8.3)
created:
23 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!