Submission #2225615

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define _p(...) (void)printf(__VA_ARGS__)
#define forr(x,arr) for(auto&& x:arr)
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) _rep3(i,0,n)
#define _rep3(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2,)(__VA_ARGS__)
#define _rrep2(i,n) _rrep3(i,0,n)
#define _rrep3(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define bit(n) (1LL<<(n))
#define sz(x) ((int)(x).size())
#define fst first
#define snd second

string DBG_DLM(int &i){return(i++==0?"":", ");}
#define DBG_B(exp){int i=0;os<<"{";{exp;}os<<"}";return os;}
template<class T>ostream&operator<<(ostream&os,vector<T>v);
template<class T>ostream&operator<<(ostream&os,set<T>v);
template<class T>ostream&operator<<(ostream&os,queue<T>q);
template<class T>ostream&operator<<(ostream&os,priority_queue<T>q);
template<class T,class K>ostream&operator<<(ostream&os,pair<T,K>p);
template<class T,class K>ostream&operator<<(ostream&os,map<T,K>mp);
template<class T,class K>ostream&operator<<(ostream&os,unordered_map<T,K>mp);
template<int I,class TPL>void DBG(ostream&os,TPL t){}
template<int I,class TPL,class H,class...Ts>void DBG(ostream&os,TPL t){os<<(I==0?"":", ")<<get<I>(t);DBG<I+1,TPL,Ts...>(os,t);}
template<class T,class K>void DBG(ostream&os,pair<T,K>p,string delim){os<<"("<<p.first<<delim<<p.second<<")";}
template<class...Ts>ostream&operator<<(ostream&os,tuple<Ts...>t){os<<"(";DBG<0,tuple<Ts...>,Ts...>(os,t);os<<")";return os;}
template<class T,class K>ostream&operator<<(ostream&os,pair<T,K>p){DBG(os,p,", ");return os;}
template<class T>ostream&operator<<(ostream&os,vector<T>v){DBG_B(forr(t,v){os<<DBG_DLM(i)<<t;});}
template<class T>ostream&operator<<(ostream&os,set<T>s){DBG_B(forr(t,s){os<<DBG_DLM(i)<<t;});}
template<class T>ostream&operator<<(ostream&os,queue<T>q){DBG_B(for(;q.size();q.pop()){os<<DBG_DLM(i)<<q.front();});}
template<class T>ostream&operator<<(ostream&os,priority_queue<T>q){DBG_B(for(;q.size();q.pop()){os<<DBG_DLM(i)<<q.top();});}
template<class T,class K>ostream&operator<<(ostream&os,map<T,K>m){DBG_B(forr(p,m){os<<DBG_DLM(i);DBG(os,p,"->");});}
template<class T,class K>ostream&operator<<(ostream&os,unordered_map<T,K>m){DBG_B(forr(p,m){os<<DBG_DLM(i);DBG(os,p,"->");});}
#define DBG_OVERLOAD(_1,_2,_3,_4,_5,_6,macro_name,...)macro_name
#define DBG_LINE(){char s[99];sprintf(s,"line:%3d | ",__LINE__);cerr<<s;}
#define DBG_OUTPUT(v){cerr<<(#v)<<"="<<(v);}
#define DBG1(v,...){DBG_OUTPUT(v);}
#define DBG2(v,...){DBG_OUTPUT(v);cerr<<", ";DBG1(__VA_ARGS__);}
#define DBG3(v,...){DBG_OUTPUT(v);cerr<<", ";DBG2(__VA_ARGS__);}
#define DBG4(v,...){DBG_OUTPUT(v);cerr<<", ";DBG3(__VA_ARGS__);}
#define DBG5(v,...){DBG_OUTPUT(v);cerr<<", ";DBG4(__VA_ARGS__);}
#define DBG6(v,...){DBG_OUTPUT(v);cerr<<", ";DBG5(__VA_ARGS__);}
#define DEBUG0(){DBG_LINE();cerr<<endl;}
#ifdef LOCAL
#define out(...){DBG_LINE();DBG_OVERLOAD(__VA_ARGS__,DBG6,DBG5,DBG4,DBG3,DBG2,DBG1)(__VA_ARGS__);cerr<<endl;}
#else
#define out(...)
#endif

using ll=long long;
using pii=pair<int,int>;using pll=pair<ll,ll>;using pil=pair<int,ll>;using pli=pair<ll,int>;
using vs=vector<string>;using vvs=vector<vs>;using vvvs=vector<vvs>;
using vb=vector<bool>;using vvb=vector<vb>;using vvvb=vector<vvb>;
using vi=vector<int>;using vvi=vector<vi>;using vvvi=vector<vvi>;
using vl=vector<ll>;using vvl=vector<vl>;using vvvl=vector<vvl>;
using vd=vector<double>;using vvd=vector<vd>;using vvvd=vector<vvd>;
using vpii=vector<pii>;using vvpii=vector<vpii>;using vvvpii=vector<vvpii>;
template<class T>bool amax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>bool amin(T&a,const T&b){return a>b?a=b,1:0;}
ll ri(){ll l;cin>>l;return l;} string rs(){string s;cin>>s;return s;}

struct HLDecomposition {
  using Edge = int;
  using Graph = vector<vector<Edge>>;

  const int n;
  const Graph &G;
  vector<int> vid, head, heavy, parent, depth, inv;

  HLDecomposition(const Graph &G, const int root = 0) : n(G.size()), G(G), vid(n, -1), head(n), heavy(n, -1), parent(n), depth(n), inv(n) {
    dfs(root, -1);
    bfs(root);
  }

  void for_each(int u, int v, function<void(int, int)> f) {
    if (vid[u] > vid[v]) swap(u, v);
    f(max(vid[head[v]], vid[u]), vid[v]);
    if (head[u] != head[v]) for_each(u, parent[head[v]], f);
  }

  private:
  int dfs(int cur, int pre) {
    parent[cur] = pre;
    int size = 1;
    int max_size = 0;
    for (auto nex : G[cur]) if (nex != pre) {
      depth[nex] = depth[cur] + 1;
      int nex_size = dfs(nex, cur);
      size += nex_size;
      if (max_size < nex_size) max_size = nex_size, heavy[cur] = nex;
    }
    return size;
  }

  void bfs(int root) {
    int k = 0;
    queue<int> q({ root });
    while (!q.empty()) {
      int h = q.front(); q.pop();
      for (int i = h; i != -1; i = heavy[i]) {
        vid[i] = k++;
        inv[vid[i]] = i;
        head[i] = h;
        for (int j : G[i]) if (j != parent[i] && j != heavy[i]) q.push(j);
      }
    }
  }
};

template <class V=int, bool MAX=true> struct SegTreeLazyAddRMQ {
  const int n;
  vector<V> cur, lazy;

  SegTreeLazyAddRMQ(int size) : n(p2(size)), cur(n * 2), lazy(n * 2){};

  void update(int begin, int end, V val) {
    update_range_rec(1, 0, n, begin, end, val);
  }

  V query(int begin, int end) {
    return query_rec(1, 0, n, begin, end);
  }

private:
  V merge(V l, V r) {
    if (MAX) return max(l, r);
    else return min(l, r);
  }

  void propagate(int node) {
    for (int child = 2 * node; child <= 2 * node + 1; child++) {
      lazy[child] += lazy[node];
      cur[child] += lazy[node];
    }
    lazy[node] = 0;
  }

  void update_range_rec(int node, int tbegin, int tend, int abegin, int aend, V val) {
    if (abegin <= tbegin && tend <= aend) {
      lazy[node] += val;
      cur[node] += val;
    }
    else {
      int mid = tbegin + (tend - tbegin + 1) / 2;
      propagate(node);
      if (abegin < mid && tbegin < aend) update_range_rec(2 * node, tbegin, mid, abegin, aend, val);
      if (abegin < tend && mid < aend) update_range_rec(2 * node + 1, mid, tend, abegin, aend, val);
      cur[node] = merge(cur[2 * node], cur[2 * node + 1]);
    }
  }

  V query_rec(int node, int tbegin, int tend, int abegin, int aend) {
    if (abegin <= tbegin && tend <= aend) {
      return cur[node];
    }
    else {
      propagate(node);
      int mid = tbegin + (tend - tbegin + 1) / 2;
      V res = MAX ? numeric_limits<V>::min() : numeric_limits<V>::max();
      if (abegin < mid && tbegin < aend) res = merge(res, query_rec(2 * node, tbegin, mid, abegin, aend));
      if (abegin < tend && mid < aend) res = merge(res, query_rec(2 * node + 1, mid, tend, abegin, aend));
      return res;
    }
  }

  static int p2(int n, int m=1) { return m >= n ? m : p2(n, m * 2); }
};

void Main() {
  int n = ri();
  vvi E(n);
  rep(i, n-1) {
    int u = ri() - 1;
    int v = ri() - 1;
    E[u].push_back(v);
    E[v].push_back(u);
  }

  HLDecomposition hld(E);
  SegTreeLazyAddRMQ<int> seg(n);

  int q = ri();
  while (q--) {
    int m = ri();
    int k = ri();
    vi V(m);
    rep(i, m) {
      int v = V[i] = ri() - 1;

      auto add = [&](int l, int r) {
        seg.update(l, r+1, 1);
      };
      hld.for_each(0, v, add);
    }

    int ans = 0;
    forr(v, V) {
      auto f = [&](int l, int r) {
        if (seg.query(l, l+1) < k) return;
        int ok = l;
        int ng = r+1;

        auto check = [&](int x) -> bool {
          return seg.query(x, x+1) >= k;
        };

        while (abs(ok - ng) > 1) {
          int mid = (ok + ng) / 2;
          bool c = check(mid);
          if (c) ok = mid;
          else ng = mid;
        }

        int x = hld.inv[ok];
        amax(ans, hld.depth[x]);
      };
      hld.for_each(0, v, f);
    }

    forr(v, V) {
      auto rev = [&](int l, int r) {
        seg.update(l, r+1, -1);
      };
      hld.for_each(0, v, rev);
    }
    cout << ans << endl;
  }
}

signed main() { cin.tie(nullptr); ios::sync_with_stdio(false); Main(); return 0; }

Submission Info

Judge Result