fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Seg {
  5.     int n;
  6.     struct Node { int mn, lz; } ;
  7.     vector<Node> st;
  8.     Seg(int n=0): n(n), st(4*n+5,{0,0}) {}
  9.     void build(int p, int l, int r, const vector<int>& base){
  10.         if(l==r){ st[p].mn = base[l]; return; }
  11.         int m=(l+r)>>1;
  12.         build(p<<1,l,m,base); build(p<<1|1,m+1,r,base);
  13.         st[p].mn = min(st[p<<1].mn, st[p<<1|1].mn);
  14.     }
  15.     void push(int p){
  16.         if(st[p].lz){
  17.             int v=st[p].lz;
  18.             st[p<<1].mn += v; st[p<<1].lz += v;
  19.             st[p<<1|1].mn += v; st[p<<1|1].lz += v;
  20.             st[p].lz=0;
  21.         }
  22.     }
  23.     void range_add(int p, int l, int r, int ql, int qr, int v){
  24.         if(ql>r || qr<l) return;
  25.         if(ql<=l && r<=qr){ st[p].mn += v; st[p].lz += v; return; }
  26.         push(p);
  27.         int m=(l+r)>>1;
  28.         range_add(p<<1,l,m,ql,qr,v);
  29.         range_add(p<<1|1,m+1,r,ql,qr,v);
  30.         st[p].mn = min(st[p<<1].mn, st[p<<1|1].mn);
  31.     }
  32.     void point_add(int p, int l, int r, int idx, int v){
  33.         if(l==r){ st[p].mn += v; return; }
  34.         push(p);
  35.         int m=(l+r)>>1;
  36.         if(idx<=m) point_add(p<<1,l,m,idx,v);
  37.         else point_add(p<<1|1,m+1,r,idx,v);
  38.         st[p].mn = min(st[p<<1].mn, st[p<<1|1].mn);
  39.     }
  40.     int get_min(){ return st[1].mn; }
  41. };
  42.  
  43. int main(){
  44.     ios::sync_with_stdio(false);
  45.     cin.tie(nullptr);
  46.     int n,m;
  47.     if(!(cin>>n>>m)) return 0;
  48.     vector<int> v(n+1);
  49.     for(int i=1;i<=n;i++) cin>>v[i];
  50.     vector<vector<int>> g(n+1);
  51.     for(int i=0;i<n-1;i++){
  52.         int a,b; cin>>a>>b;
  53.         g[a].push_back(b);
  54.         g[b].push_back(a);
  55.     }
  56.     vector<int> tin(n+1), tout(n+1), depth(n+1), order(n+1), par(n+1,-1);
  57.     int timer=0;
  58.     function<void(int,int)> dfs = [&](int u,int p){
  59.         par[u]=p;
  60.         tin[u]=++timer; order[timer]=u;
  61.         for(int w: g[u]) if(w!=p){
  62.             depth[w]=depth[u]+1;
  63.             dfs(w,u);
  64.         }
  65.         tout[u]=timer;
  66.     };
  67.     dfs(1,0);
  68.     const int INF = 1e9;
  69.     vector<int> base(timer+1, INF);
  70.     Seg seg(timer);
  71.     seg.build(1,1,timer,base);
  72.     vector<int> mask(timer+1, INF);
  73.     auto activate = [&](int u){
  74.         int pos=tin[u];
  75.         int newMask = -(depth[u]+1);
  76.         seg.point_add(1,1,timer,pos,newMask - mask[pos]);
  77.         mask[pos]=newMask;
  78.         seg.range_add(1,1,timer,tin[u],tout[u],+1);
  79.     };
  80.     auto deactivate = [&](int u){
  81.         int pos=tin[u];
  82.         int newMask = INF;
  83.         seg.point_add(1,1,timer,pos,newMask - mask[pos]);
  84.         mask[pos]=newMask;
  85.         seg.range_add(1,1,timer,tin[u],tout[u],-1);
  86.     };
  87.     vector<vector<int>> byVal(m+2);
  88.     for(int i=1;i<=n;i++) byVal[v[i]].push_back(i);
  89.     vector<int> occ(m+2,0);
  90.     int distinct=0, dup=0, activeCnt=0;
  91.     auto addVal = [&](int x){
  92.         for(int u: byVal[x]){ activate(u); activeCnt++; }
  93.         occ[x] += (int)byVal[x].size();
  94.         if(occ[x]>0 && occ[x]-(int)byVal[x].size()==0) distinct++;
  95.         if(occ[x]>=2) dup++;
  96.     };
  97.     auto removeVal = [&](int x){
  98.         if(occ[x]>=2) dup--;
  99.         if(occ[x]>0 && occ[x]-(int)byVal[x].size()==0) distinct--;
  100.         for(int u: byVal[x]){ deactivate(u); activeCnt--; }
  101.         occ[x] -= (int)byVal[x].size();
  102.     };
  103.     int ans=0;
  104.     int L=1;
  105.     for(int R=1; R<=m; R++){
  106.         addVal(R);
  107.         while(L<=R){
  108.             bool ok_gap = (distinct == R-L+1);
  109.             bool ok_dup = (dup==0);
  110.             bool ok_tree = (activeCnt==0) || (seg.get_min()==0);
  111.             if(ok_gap && ok_dup && ok_tree){
  112.                 ans = max(ans, activeCnt);
  113.                 break;
  114.             }else{
  115.                 removeVal(L);
  116.                 L++;
  117.             }
  118.         }
  119.         if(L>R){ L=R+1; }
  120.     }
  121.     cout<<ans<<"\n";
  122.     return 0;
  123. }
  124.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
4 4
2 1 3 4
1 2
1 3
3 4
stdout
copy 
3
https://ideone.com/xNUci0
language:
C++14 (gcc 8.3)
created:
11 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!