fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.  
  8.     int n, m;
  9.     if(!(cin >> n >> m)) return 0;
  10.     vector<int> v(n + 1);
  11.     for (int i = 1; i <= n; ++i) cin >> v[i];
  12.  
  13.     vector<vector<int>> children(n + 1);
  14.     vector<int> parent(n + 1, 0);
  15.  
  16.     for (int i = 1; i < n; ++i) {
  17.         int a, b;              // a là quản lý trực tiếp của b
  18.         cin >> a >> b;
  19.         parent[b] = a;
  20.         children[a].push_back(b);
  21.     }
  22.  
  23.     // danh sách các node theo giá trị bài
  24.     vector<vector<int>> byValue(m + 1);
  25.     for (int u = 1; u <= n; ++u) if (1 <= v[u] && v[u] <= m) byValue[v[u]].push_back(u);
  26.  
  27.     vector<int> freq(m + 1, 0);
  28.     vector<char> inside(n + 1, 0);
  29.  
  30.     auto add_node = [&](int u, long long &bad_edges, long long &dupCnt){
  31.         // thêm u vào cửa sổ
  32.         inside[u] = 1;
  33.         if (++freq[v[u]] == 2) ++dupCnt; // vừa xuất hiện trùng
  34.         // cạnh với parent
  35.         if (parent[u] != 0 && !inside[parent[u]]) ++bad_edges;
  36.         // cạnh với con
  37.         for (int c : children[u]) {
  38.             if (inside[c]) {
  39.                 // trước đó cạnh c trong, u ngoài → bad; giờ thì hết bad
  40.                 --bad_edges;
  41.             }
  42.         }
  43.     };
  44.  
  45.     auto remove_node = [&](int u, long long &bad_edges, long long &dupCnt){
  46.         // bỏ u ra khỏi cửa sổ
  47.         // cạnh với parent
  48.         if (parent[u] != 0 && !inside[parent[u]]) --bad_edges;
  49.         // cạnh với con
  50.         for (int c : children[u]) {
  51.             if (inside[c]) {
  52.                 // giờ trở thành c trong, u ngoài → bad
  53.                 ++bad_edges;
  54.             }
  55.         }
  56.         if (--freq[v[u]] == 1) --dupCnt;  // vừa bỏ bớt trùng
  57.         inside[u] = 0;
  58.     };
  59.  
  60.     long long ans = 0;
  61.     long long bad_edges = 0; // số cạnh có con trong, cha ngoài
  62.     long long dupCnt = 0;    // số giá trị xuất hiện >= 2 lần
  63.     int L = 1;
  64.  
  65.     // đảm bảo L luôn <= v[root]
  66.     auto ensure_root_left = [&](){
  67.         if (L > v[1]) {
  68.             // đẩy L lùi lại sẽ không thuận tiện trong hai con trỏ tăng dần,
  69.             // vì thế ta chỉ cho phép đếm khi L <= v[root] <= R (xử lý ở vòng while bên dưới).
  70.             return;
  71.         }
  72.     };
  73.  
  74.     // hai con trỏ trên [L, R]
  75.     for (int R = 1; R <= m; ++R) {
  76.         // thêm tất cả node có v = R
  77.         for (int u : byValue[R]) add_node(u, bad_edges, dupCnt);
  78.  
  79.         // dịch L cho đến khi thỏa 3 điều kiện:
  80.         // 1) không trùng,
  81.         // 2) không có cạnh xấu,
  82.         // 3) L <= v[root] <= R  (root thuộc cửa sổ).
  83.         while (L <= R && (dupCnt > 0 || bad_edges > 0 || !(L <= v[1] && v[1] <= R))) {
  84.             for (int u : byValue[L]) if (inside[u]) remove_node(u, bad_edges, dupCnt);
  85.             ++L;
  86.         }
  87.  
  88.         if (L <= R && (dupCnt == 0 && bad_edges == 0 && (L <= v[1] && v[1] <= R))) {// Với R cố định, mọi L hiện tại tạo ra đúng một khoảng hợp lệ kết thúc ở R
  89.             // (theo cách ta đã đẩy L tới nhỏ nhất thỏa điều kiện).
  90.             ans += (L <= R);
  91.         }
  92.     }
  93.  
  94.     cout << ans << '\n';
  95.     return 0;
  96. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
4 6
3 4 5 6
1 2
1 3
2 4
stdout
copy 
4
https://ideone.com/NBLgvv
language:
C++14 (gcc 8.3)
created:
5 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!