fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. constexpr int N = 1e6 + 5;
  7.  
  8. // Cây Fenwick dùng để cập nhật và tính tổng nhanh trong O(log)
  9. struct FenwickTree
  10. {
  11.     int n, a[N];
  12.     FenwickTree()
  13.     {
  14.         memset(a, 0, sizeof a);
  15.     }
  16.  
  17.     void Update(int p, int v)
  18.     {
  19.         for (; p <= n; p += p & -p)
  20.             a[p] += v;
  21.     }
  22.  
  23.     int Get(int p)
  24.     {
  25.         int ans = 0;
  26.         for (; p; p -= p & -p)
  27.             ans += a[p];
  28.         return ans;
  29.     }
  30.  
  31.     int Get(int l, int r)
  32.     {
  33.         return Get(r) - Get(l - 1);
  34.     }
  35. } f;
  36.  
  37.  
  38. int n, q;
  39. vector<int> adj[N];
  40. int a[N];
  41. int in[N], out[N], l;
  42. int par[N][20], ranks[N];
  43.  
  44. struct com
  45. {
  46.     bool operator()(const int &x, const int &y) const
  47.     {
  48.         return in[x] < in[y];
  49.     }
  50. };
  51.  
  52. multiset<int, com> s[N]; // s[x] chứa các đỉnh có bông hoa có màu x, 
  53.                          // dùng multiset vì một đỉnh có thể xuất hiện nhiều lần
  54.  
  55. void Read()
  56. {
  57.     cin >> n;
  58.  
  59.     for (int i = 1; i <= n; ++i)
  60.         cin >> a[i];
  61.  
  62.     for (int i = 1; i < n; ++i)
  63.     {
  64.         int u, v;
  65.         cin >> u >> v;
  66.         adj[u].emplace_back(v);
  67.         adj[v].emplace_back(u);
  68.     }
  69.  
  70.     cin >> q;
  71. }
  72.  
  73. // dfs để tạo ra dfs order (dfs decomposition)
  74. void dfs(int v, int p = -1)
  75. {
  76.     in[v] = ++l;
  77.  
  78.     for (int i = 1; i < 20; ++i)
  79.         par[v][i] = par[par[v][i - 1]][i - 1];
  80.  
  81.     for (auto i : adj[v])
  82.         if (i != p)
  83.         {
  84.             par[i][0] = v;
  85.             ranks[i] = ranks[v] + 1;
  86.             dfs(i, v);
  87.         }
  88.  
  89.     out[v] = l;
  90. }
  91.  
  92. int LCA(int u, int v)
  93. {
  94.     if (ranks[u] < ranks[v])
  95.         swap(u, v);
  96.  
  97.     for (int i = 19; ~i; --i)
  98.         if (ranks[par[u][i]] >= ranks[v])
  99.             u = par[u][i];
  100.  
  101.     for (int i = 19; ~i; --i)
  102.         if (par[u][i] != par[v][i])
  103.         {
  104.             u = par[u][i];
  105.             v = par[v][i];
  106.         }
  107.  
  108.     return u == v ? u : par[u][0];
  109. }
  110.  
  111. // Mọc giữa đỉnh thứ v
  112. // Một bông hoa màu x
  113. void Add(int x, int v)
  114. {
  115.     auto i = s[x].lower_bound(v);
  116.     auto j = prev(i);
  117.     f.Update(in[LCA(*i, *j)], 1);
  118.  
  119.     f.Update(in[v], 1);
  120.     f.Update(in[LCA(*i, v)], -1);
  121.     f.Update(in[LCA(v, *j)], -1);
  122.  
  123.     s[x].insert(v);
  124. }
  125.  
  126. // Hoa v-màu hoa chóng tàn phái
  127. // Chớm nở đỉnh v, hoa tàn hoa để cho ai...
  128. void Erase(int x, int v)
  129. {
  130.     auto i = s[x].lower_bound(v);
  131.     assert(i != s[x].end() && *i == v);
  132.  
  133.     auto t = prev(i),
  134.          j = next(i);
  135.  
  136.     f.Update(in[v], -1);
  137.     f.Update(in[LCA(v, *j)], 1);
  138.     f.Update(in[LCA(*t, v)], 1);
  139.  
  140.     f.Update(in[LCA(*j, *t)], -1);
  141.  
  142.     s[x].erase(i);
  143. }
  144.  
  145. void Solve()
  146. {
  147.     adj[n + 1].emplace_back(1);
  148.     adj[n + 1].emplace_back(n + 2);
  149.     ranks[n + 1] = 1;
  150.     dfs(n + 1);
  151.  
  152.     f.n = l;
  153.  
  154.     for (int i = 0; i < N; ++i)
  155.     {
  156.         s[i].insert(n + 2);
  157.         s[i].insert(n + 1);
  158.     }
  159.  
  160.     for (int i = 1; i <= n; ++i)
  161.         if (a[i] != -1)
  162.             Add(a[i], i);
  163.  
  164.     int ans = 0;
  165.  
  166.     q *= 2;
  167.  
  168.     while (q--)
  169.     {
  170.         string s;
  171.         int u, v;
  172.         cin >> s >> u >> v;
  173.  
  174.         if (s == "BLOOM")
  175.             Add(u ^ ans, v ^ ans);
  176.         else if (s == "DISSOLVE")
  177.             Erase(u ^ ans, v ^ ans);
  178.         else
  179.         {
  180.             if (ranks[u] < ranks[v])
  181.                 swap(u, v);
  182.  
  183.             cout << (ans = f.Get(in[u], out[u])) << "\n";
  184.         }
  185.     }
  186. }
  187.  
  188. int32_t main()
  189. {
  190.     ios::sync_with_stdio(0);
  191.     cin.tie(0);
  192.     cout.tie(0);
  193.     Read();
  194.     Solve();
  195. }
Success #stdin #stdout 0.25s 173544KB
comments (?)
stdin
copy 
5
1 -1 3 -1 5
1 3
2 4
1 5
5 4
5
BLOOM 2 2
TAKE 4 5
DISSOLVE 2 2
TAKE 2 4
BLOOM 5 4
TAKE 1 3
DISSOLVE 5 5
TAKE 4 2
BLOOM 2 0
TAKE 1 5
stdout
copy 
1
1
0
1
2
https://ideone.com/qT17Ae
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!