fork download 
  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.  
  11.     vector<int> v(n + 1);
  12.     for (int i = 1; i <= n; ++i) cin >> v[i];
  13.  
  14.     vector<vector<int>> child(n + 1);
  15.     vector<int> par(n + 1, 0);
  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.         par[b] = a;
  20.         child[a].push_back(b);
  21.     }
  22.  
  23.     // Euler tour: tin/tout
  24.     vector<int> tin(n + 1), tout(n + 1);
  25.     int timer = 0;
  26.     {
  27.         vector<pair<int,int>> st;
  28.         st.reserve(2*n);
  29.         st.emplace_back(1, 0);
  30.         while (!st.empty()) {
  31.            auto tmp= st.back(); st.pop_back();
  32.            int u=tmp.first, state=tmp.second;
  33.             if (state == 0) {
  34.                 tin[u] = ++timer;
  35.                 st.emplace_back(u, 1);
  36.                 for (int c : child[u]) st.emplace_back(c, 0);
  37.             } else {
  38.                 tout[u] = timer;
  39.             }
  40.         }
  41.     }
  42.  
  43.     // Với mỗi giá trị t (1..m), lưu danh sách các tin của các nút có giá trị t
  44.     vector<vector<int>> occ(m + 1);
  45.     for (int u = 1; u <= n; ++u) {
  46.         if (1 <= v[u] && v[u] <= m) occ[v[u]].push_back(tin[u]);
  47.     }
  48.     for (int t = 1; t <= m; ++t) {
  49.         sort(occ[t].begin(), occ[t].end()); // phòng khi không theo Euler sẵn
  50.     }
  51.  
  52.     // bestX[y] = max x sao cho tồn tại cây con có "khoảng trống" (x, y) (y - x >= 2)
  53.     vector<int> bestX(m + 1, 0);
  54.  
  55.     // Hàm kiểm tra "trong cây con u có xuất hiện giá trị t?"
  56.     auto in_subtree = [&](int u, int t) -> bool {
  57.         const auto &vec = occ[t];
  58.         if (vec.empty()) return false;
  59.         auto it = lower_bound(vec.begin(), vec.end(), tin[u]);
  60.         return (it != vec.end() && *it <= tout[u]);
  61.     };
  62.  
  63.     // Duyệt từng nút, quét t=1..m để lấy các cặp liên tiếp trong S_u
  64.     for (int u = 1; u <= n; ++u) {
  65.         int prev = -1;
  66.         for (int t = 1; t <= m; ++t) {
  67.             if (!in_subtree(u, t)) continue;
  68.             if (prev != -1) {
  69.                 if (t - prev >= 2) {
  70.                     // có "lỗ" giữa prev và t trong cây con u
  71.                     bestX[t] = max(bestX[t], prev);
  72.                 }
  73.             }
  74.             prev = t;
  75.         }
  76.     }
  77.  
  78.     // badLeft[R] = max_{y<=R} bestX[y]
  79.     vector<int> badLeft(m + 1, 0);
  80.     for (int R = 1; R <= m; ++R) {
  81.         badLeft[R] = max(badLeft[R - 1], bestX[R]);
  82.     }
  83.  
  84.     // lastMissing[R] = giá trị bị thiếu (không ai có) gần nhất ≤ R; nếu không thiếu -> giữ nguyên
  85.     vector<int> lastMissing(m + 1, 0);
  86.     for (int t = 1; t <= m; ++t) {
  87.         lastMissing[t] = lastMissing[t - 1];
  88.         if (occ[t].empty()) lastMissing[t] = t;
  89.     }
  90.  
  91.     // Tính đáp án
  92.     long long ans = 0;
  93.     int rootVal = v[1];
  94.     if (rootVal >= 1 && rootVal <= m) {
  95.         for (int R = 1; R <= m; ++R) {
  96.             if (R < rootVal) continue; // phải chứa rootint lower = max(badLeft[R], lastMissing[R]);
  97.             int toupper = min(R, rootVal), tolower = max(badLeft[R], lastMissing[R]);
  98.             if (toupper > tolower) ans += (toupper - tolower);
  99.         }
  100.     } else {
  101.         // root có giá trị ngoài [1..m] thì không có đoạn nào
  102.         ans = 0;
  103.     }
  104.  
  105.     cout << ans << "\n";
  106.     return 0;
  107. }
  108.  
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin 
3 5
1 2 4
1 2
2 3
stdout 
2
https://ideone.com/pj87YW
language:
C++14 (gcc 8.3)
created:
13 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!