Submission #584342

---

Source Code Expand

#define _CRT_SECURE_NO_WARNINGS
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// #define int ll
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
#define all(c) begin(c), end(c)
#define range(i,a,b) for(ll i=a; i<ll(b); i++)
#define rep(i,b) range(i,0,b)
#define rangei(i,a,b) for(ll a=a;i<=ll(b);i++)
#define repi(i,b) rangei(i,1,b)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
template<class T> ostream & operator << (ostream &os, vector<T> const &);
template<int n, class...T>
typename enable_if<(n>=sizeof...(T))>::type
_ot(ostream &, tuple<T...> const &){}
template<int n, class...T>
typename enable_if<(n< sizeof...(T))>::type
_ot(ostream &os, tuple<T...> const &t){
    os << (n==0?"":" ") << get<n>(t); _ot<n+1>(os, t);
}
    template<class...T>
    ostream & operator << (ostream &os, tuple<T...> const &t){
        _ot<0>(os, t); return os;
    }
template<class T, class U>
ostream & operator<<(ostream &os, pair<T,U> const &p){
    return os << "(" << p.first << ", " << p.second << ") ";
}
template<class T>
ostream & operator<<(ostream &os, vector<T> const &v){
    rep(i,v.size()) os << v[i] << (i+1==(int)v.size()?"":" "); return os;
}
#ifdef DEBUG
#define dump(...) (cerr << #__VA_ARGS__ << " = " << mt(__VA_ARGS__) \
                   << " [" << __LINE__ << "]" << endl)
#else
#define dump(...)
#endif
void fastios(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#define endl '\n'
}
template<class T>
size_t uniq(vector<T> &v){
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    return v.size();
}
template<class T>
size_t uniq(T *l, size_t n){
    sort(l,l+n);
    return unique(l,l+n) - l;
}
#define mems(arr,val) memset(arr,val,sizeof(arr));
int const mod = 1000000007;
int const inf = numeric_limits<int>::max()/8;

typedef int Weight;
struct Edge {
    int src, dst;
    Edge(int src_, int dst_) :
        src(src_), dst(dst_) { }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

struct HLDecomp {
    const Graph &g;
    int n;
    vector<vector<int>> chains;
    vector<int> parent, size, depth, head, last, next, prev, chain, at;
    HLDecomp(const Graph &g_)
        : g(g_), n(g.size()), chains(0),
          parent(n, 0), size(n, 0), depth(n, -1), head(n, 0),
          last(n, 0), next(n, -1), prev(n, -1), chain(n, -1), at(n, 0){
        decompose();
    }
    int goUp(int v) const { return parent[head[v]]; }
    pair<int, int> getIndex(int v) const { return make_pair(chain[v], at[v]); }

    void decompose(const int root = 0){
        static int stk[600010], k = 0;
        stk[k++] = root; parent[root] = -1; depth[root] = 0;
        while(k){
            int v = stk[--k];
            if(v >= 0){
                stk[k++] = ~v;
                for(auto &e : g[v]){
                    int ch = e.dst;
                    if(depth[ch] == -1){
                        depth[ch] = depth[v] + 1;
                        parent[ch] = v;
                        stk[k++] = ch;
                    }
                }
            } else {
                int m = 0; v = ~v; size[v] = 1;
                for(auto &e : g[v]){
                    int ch = e.dst;
                    if(parent[v] == ch) continue;
                    size[v] += size[ch];
                    if(m < size[ch]){ m = size[ch]; next[v] = ch; }
                }
            }
        }

        k = 0;
        stk[k++] = root;
        while(k){
            int h = stk[--k];
            for(auto &e : g[h]) if(parent[h] != e.dst) stk[k++] = e.dst;
            if(chain[h] != -1) continue;
            chains.push_back(vector<int>());
            vector<int> & path = chains.back();
            int cur = h;
            while(cur != -1){ path.push_back(cur); cur = next[cur]; }
            for(int i = 0; i < (int)path.size(); i++){
                int v = path[i];
                head[v] = path.front(); last[v] = path.back();
                next[v] = i+1 != (int)path.size() ? path[i+1] : -1;
                prev[v] = i != 0 ? path[i-1] : -1; chain[v] = chains.size() - 1; at[v] = i;
            }
        }
    }
    int lca(int u, int v){
        while(chain[u] != chain[v]){
            if(depth[head[u]] > depth[head[v]]) u = goUp(u);
            else v = goUp(v);
        }
        return depth[u] < depth[v] ? u : v;
    }

    int solve(vector<int> const & vs, int k) const {
        map<int,vector<int>> pathes;
        for(int v : vs){
            while(v != -1){
                pathes[chain[v]].push_back(at[v]);
                v = goUp(v);
            }
        }
        int ans = -1;
        for(auto & c_path : pathes){
            int c = c_path.first;
            auto & path = c_path.second;
            if((int)path.size() >= k){
                sort(path.rbegin(), path.rend());
                int v = chains[c][path[k-1]];
                ans = max(ans, depth[v]);
            }
        }
        return ans;
    }
};

signed main(){
    fastios();
    int N;
    while(cin >> N){
        Graph g(N);
        rep(i,N-1){
            int x,y;
            cin >> x >> y;
            x--; y--;
            g[x].eb(x,y);
            g[y].eb(y,x);
        }
        HLDecomp hld(g);
        hld.decompose();
        int Q;
        cin >> Q;
        rep(qq,Q){
            int M,K;
            cin >> M >> K;
            vector<int> ms(M);
            rep(i,M) cin >> ms[i], ms[i]--;
            cout << hld.solve(ms,K) << '\n';
        }
    }
}

Submission Info

Judge Result