fork download 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. const int MAXN = 70000 + 5;
  7. const int MAXM = 2000 + 5;
  8.  
  9. int n, m, a[MAXN];
  10. vector<int> g[MAXN];
  11.  
  12. int st[MAXN], ed[MAXN], timer_ = 0;
  13. vector<int> occ[MAXM];
  14.  
  15. void dfs(int u){
  16.     st[u] = ++timer_;
  17.     for(int v: g[u]) dfs(v);
  18.     ed[u] = timer_;
  19. }
  20.  
  21. inline bool in_sub(int u, int val){ 
  22.     const auto& cur = occ[val];
  23.     auto it = lower_bound(cur.begin(), cur.end(), st[u]);
  24.     return (it!=cur.end() && *it<=ed[u]);
  25. }
  26.  
  27. int main(){
  28.     ios::sync_with_stdio(false);
  29.     cin.tie(nullptr);
  30.  
  31.     if (fopen("o.inp","r")){
  32.         freopen("o.inp","r",stdin);
  33.         freopen("o.out","w",stdout);
  34.     }
  35.  
  36.     cin >> n >> m;
  37.     for (int i=1;i<=n;i++) cin >> a[i];
  38.     for (int i=1;i<=n-1;i++){
  39.         int u,v; cin >> u >> v;
  40.         g[u].push_back(v);
  41.     }
  42.  
  43.     dfs(1);
  44.     for (int i=1;i<=n;i++) occ[a[i]].push_back(st[i]);
  45.     for (int v=1; v<=m; v++) sort(occ[v].begin(), occ[v].end());
  46.     vector<int> present(m+2,0);
  47.     for(int v=1; v<=m; v++) present[v] = !occ[v].empty();
  48.     vector<int> next_missing(m+2, m+1);
  49.     int nxt = m+1;
  50.     for(int L=m; L>=1; --L){
  51.         if(!present[L]) nxt = L; 
  52.         next_missing[L] = nxt;
  53.     }
  54.     vector<vector<pair<int,int>>> activate_at(m+2); 
  55.     for (int p=1; p<=n; ++p){
  56.         for (int c: g[p]){
  57.             static vector<char> pres; pres.assign(m+2, 0);
  58.             for (int v=1; v<=m; ++v){
  59.                 if (in_sub(c, v)) pres[v]=1;
  60.             }
  61.             static vector<int> next_ge; next_ge.assign(m+2, m+1); 
  62.             int last = m+1;
  63.             for (int v=m; v>=1; --v){
  64.                 if (pres[v]) last = v;
  65.                 next_ge[v] = last;
  66.             }
  67.             for (int L=1; L<=m; ++L){
  68.                 int R0 = next_ge[L];
  69.                 if (R0<=m){
  70.                     activate_at[R0].push_back({L, a[p]});
  71.                 }
  72.             }
  73.         }
  74.     }
  75.  
  76.     long long ans = 0;
  77.  
  78.  
  79.     for (int L=1; L<=m; ++L){
  80.         int needR = a[1];              
  81.         if (needR < L) { 
  82.             continue;
  83.         }
  84.         int cutR = next_missing[L]-1;   
  85.         bool ok = true;
  86.  
  87.  
  88.         for (int R=L; R<=m && ok; ++R){
  89.             if (R > cutR) break;
  90.  
  91.  
  92.             for (auto [L0, ap] : activate_at[R]){
  93.                 if (L0 != L) continue;
  94.                 if (ap < L){ ok = false; break; }
  95.                 if (ap > needR) needR = ap;
  96.             }
  97.             if (!ok) break;
  98.  
  99.             if (R >= needR) ans++;
  100.         }
  101.     }
  102.  
  103.     cout << ans << '\n';
  104.     return 0;
  105. }
  106.  
Success #stdin #stdout 0.01s 5348KB
comments (?)
stdin 
4 6
3 4 5 6
1 2
1 3
2 4
stdout 
4
https://ideone.com/8yHuCW
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!