fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 300005;
  5.  
  6. int n, k, m;
  7. int c[MAXN];
  8. vector<int> adj[MAXN];
  9.  
  10. int tin[MAXN], tout[MAXN], timer = 0;
  11. int parent_node[MAXN], depth[MAXN], heavy[MAXN], head[MAXN];
  12. set<int> color_pos[MAXN]; // Lưu các vị trí tin[] của mỗi màu
  13.  
  14. // Segment Tree với Lazy Propagation quản lý giá trị trên khoảng [1, n] tương ứng với thứ tự DFS
  15. int st[MAXN * 4], lazy[MAXN * 4];
  16.  
  17. void push(int node) {
  18.     if (lazy[node] != 0) {
  19.         st[node * 2] += lazy[node];
  20.         lazy[node * 2] += lazy[node];
  21.         st[node * 2 + 1] += lazy[node];
  22.         lazy[node * 2 + 1] += lazy[node];
  23.         lazy[node] = 0;
  24.     }
  25. }
  26.  
  27. void update(int node, int l, int r, int ql, int qr, int val) {
  28.     if (ql > r || qr < l) return;
  29.     if (ql <= l && r <= qr) {
  30.         st[node] += val;
  31.         lazy[node] += val;
  32.         return;
  33.     }
  34.     push(node);
  35.     int mid = (l + r) / 2;
  36.     update(node * 2, l, mid, ql, qr, val);
  37.     update(node * 2 + 1, mid + 1, r, ql, qr, val);
  38.     st[node] = max(st[node * 2], st[node * 2 + 1]); // Hoặc dấu + tùy cách gộp đoạn, ở đây quản lý số màu max hoặc tổng tùy ý nhưng thực tế các khoảng tổ tiên cộng dồn
  39. }
  40.  
  41. // Thay đổi hàm update cho chuẩn dạng cộng dồn trên đoạn
  42. void range_add(int node, int l, int r, int ql, int qr, int val) {
  43.     if (ql > r || qr < l) return;
  44.     if (ql <= l && r <= qr) {
  45.         st[node] += val;
  46.         lazy[node] += val;
  47.         return;
  48.     }
  49.     push(node);
  50.     int mid = (l + r) / 2;
  51.     range_add(node * 2, l, mid, ql, qr, val);
  52.     range_add(node * 2 + 1, mid + 1, r, ql, qr, val);
  53.     st[node] = st[node * 2] + st[node * 2 + 1]; // Nếu dùng Segment Tree tổng (Sum Segment Tree)
  54. }
  55.  
  56. int query_point(int node, int l, int r, int idx) {
  57.     if (l == r) return st[node];
  58.     push(node);
  59.     int mid = (l + r) / 2;
  60.     if (idx <= mid) return query_point(node * 2, l, mid, idx);
  61.     else return query_point(node * 2 + 1, mid + 1, r, idx);
  62. }
  63.  
  64. // Hàm tìm LCA nhanh dùng HLD
  65. void dfs_sz(int u, int p) {
  66.     depth[u] = depth[p] + 1;
  67.     parent_node[u] = p;
  68.     int max_sz = 0;
  69.     for (int v : adj[u]) {
  70.         if (v != p) {
  71.             dfs_sz(v, u);
  72.             int sz = tout[v] - tin[v] + 1;
  73.             if (sz > max_sz) {
  74.                 max_sz = sz;
  75.                 heavy[u] = v;
  76.             }
  77.         }
  78.     }
  79. }
  80.  
  81. void dfs_hld(int u, int h) {
  82.     head[u] = h;
  83.     tin[u] = ++timer;
  84.     if (heavy[u] != 0) {
  85.         dfs_hld(heavy[u], h);
  86.     }
  87.     for (int v : adj[u]) {
  88.         if (v != parent_node[u] && v != heavy[u]) {
  89.             dfs_hld(v, v);
  90.         }
  91.     }
  92.     tout[u] = timer;
  93. }
  94.  
  95. int get_lca(int u, int v) {
  96.     while (head[u] != head[v]) {
  97.         if (depth[head[u]] > depth[head[v]]) u = parent_node[head[u]];
  98.         else v = parent_node[head[v]];
  99.     }
  100.     return depth[u] < depth[v] ? u : v;
  101. }
  102.  
  103. // Kiểm tra quan hệ tổ tiên
  104. bool is_ancestor(int u, int v) {
  105.     return tin[u] <= tin[v] && tout[v] <= tout[u];
  106. }
  107.  
  108. // Khởi tạo ban đầu số màu phân biệt cho cây con mỗi đỉnh
  109. set<int> cur_colors[MAXN];
  110. void dfs_init(int u, int p) {
  111.     cur_colors[u].insert(c[u]);
  112.     for (int v : adj[u]) {
  113.         if (v != p) {
  114.             dfs_init(v, u);
  115.             if (cur_colors[v].size() > cur_colors[u].size()) {
  116.                 swap(cur_colors[u], cur_colors[v]);
  117.             }
  118.             for (int col : cur_colors[v]) {
  119.                 cur_colors[u].insert(col);
  120.             }
  121.             set<int>().swap(cur_colors[v]);
  122.         }
  123.     }
  124. }
  125.  
  126. // Cập nhật khi thêm một đỉnh u có màu col vào cấu trúc quản lý
  127. void add_color(int u, int col) {
  128.     // Thêm vào set quản lý vị trí tin
  129.     auto it = color_pos[col].insert(tin[u]).first;
  130.     // Xác định các điểm ảnh hưởng trên đường đi từ u lên gốc
  131.     // Thực chất mỗi màu mới xuất hiện trong cây con của các tổ tiên nằm từ u lên đến LCA hoặc đỉnh chặn gần nhất.
  132. }
  133.  
  134. int main() {
  135.     ios_base::sync_with_stdio(false);
  136.     cin.tie(NULL);
  137.  
  138.     if (!(cin >> n >> k >> m)) return 0;
  139.     for (int i = 1; i <= n; ++i) {
  140.         cin >> c[i];
  141.     }
  142.     for (int i = 0; i < n - 1; ++i) {
  143.         int u, v;
  144.         cin >> u >> v;
  145.         adj[u].push_back(v);
  146.         adj[v].push_back(u);
  147.     }
  148.  
  149.     dfs_sz(1, 0);
  150.     dfs_hld(1, 0);
  151.  
  152.     for (int i = 1; i <= n; ++i) {
  153.         color_pos[c[i]].insert(tin[i]);
  154.     }
  155.  
  156.     dfs_init(1, 0);
  157.     for (int i = 1; i <= n; ++i) {
  158.         // Nạp giá trị khởi tạo vào Segment Tree (quản lý tổng hoặc điểm)
  159.         // Mỗi đỉnh i có cur_colors[i].size() màu phân biệt trong cây con
  160.         // Ta có thể dùng point update cho vị trí tin[i]
  161.     }
  162.  
  163.     while (m--) {
  164.         int type;
  165.         cin >> type;
  166.         if (type == 1) {
  167.             int a, b;
  168.             cin >> a >> b;
  169.             // Xử lý đổi màu a từ c[a] sang b
  170.             c[a] = b;
  171.         } else {
  172.             int a;
  173.             cin >> a;
  174.             cout << query_point(1, 1, n, tin[a]) << "\n";
  175.         }
  176.     }
  177.  
  178.     return 0;
  179. }
Success #stdin #stdout 0.01s 42904KB
comments (?)
stdin
copy 
5 5 5
3 4 1 1 2
1 2
1 3
2 4
2 5
2 2
2 1
1 2 1
2 2
2 1
stdout
copy 
0
0
0
0
https://ideone.com/LYl3h5
language:
C++14 (gcc 8.3)
created:
9 days 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!