天下一プログラマーコンテスト2015本戦 F 根付き木のみさわさん

struct HeavyLightDecomposition {
    int size;
    vector<vector<int>> g;
    HeavyLightDecomposition(int n_) : size(n_), g(n_) {}
    // heavy edgeからなるパスの頂点列
    struct Node {
        Node() : par(0), subt_size(0), dep(-1),
                 heavy_begin(0), heavy_end(0), heavy_next(-1),
                 heavy(-1), heavy_index(0) {
        }
        // 親，部分木の大きさ，深さ
        int par, subt_size, dep;
        // 属する heavy の最初，最後，次
        int heavy_begin, heavy_end, heavy_next;
        // 属する heavy の id, その中での index
        int heavy, heavy_index;
    };
    vector<vector<int>> heavys;
    vector<Node> nodes;
    Node & ac(int v){ return nodes[v]; }
    Node const & ac(int v) const { return nodes[v]; }
    void add_edge(int a, int b){ g[a].push_back(b); g[b].push_back(a); }
    // 属する頂点が刺さっている heavy の付け根に移る．ないなら -1．
    int upper(int & v) const { return ac(ac(v).heavy_begin).par; }
    void decomposition(const int root = 0){
        nodes.assign(size,Node());
        vector<int> stk = { root };
        ac(root).par = -1;
        ac(root).dep = 0;
        while(stk.size()){
            const int v = stk.back();
            stk.pop_back();
            if(v >= 0){
                stk.push_back(~v);
                for(const int ch : g[v]){
                    if(ac(ch).dep != -1) continue;
                    ac(ch).dep = ac(v).dep + 1;
                    ac(ch).par = v;
                    stk.push_back(ch);
                }
            } else {
                const int u = ~v;
                ac(u).subt_size = 1;
                int m = 0;
                for(int ch : g[u]){
                    if(ac(u).par == ch) continue;
                    ac(u).subt_size += ac(ch).subt_size;
                    if(m < ac(ch).subt_size){
                        m = ac(ch).subt_size;
                        ac(u).heavy_next = ch;
                    }
                }
            }
        }

        heavys.clear();
        stk = { root };
        while(stk.size()){
            const int head = stk.back();
            stk.pop_back();
            for(const int ch : g[head]){
                if(ac(head).par == ch) continue;
                stk.push_back(ch);
            }
            if(ac(head).heavy != -1) continue;
            vector<int> path;
            int cur = head;
            while(cur != -1){
                path.push_back(cur);
                cur = ac(cur).heavy_next;
            }
            for(int i = 0; i < (int)path.size(); i++){
                const int v = path[i];
                ac(v).heavy = heavys.size();
                ac(v).heavy_begin = path.front();
                ac(v).heavy_end = path.back();
                ac(v).heavy_index = i;
            }
            heavys.push_back(path);
        }
    }

    // TNK1 2015 final F
    int solve(vector<int> const & vs, int k) const {
        map<int,vector<int>> pathes;
        for(int v : vs){
            while(v != -1){
                pathes[ac(v).heavy].push_back(ac(v).heavy_index);
                v = upper(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.begin(), path.end());
                reverse(path.begin(), path.end());
                int v = heavys[c][path[k-1]];
                ans = max(ans, ac(v).dep);
            }
        }
        return ans;
    }
};

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    HeavyLightDecomposition g(N);
    rep(i,N-1){
        int x,y;
        cin >> x >> y;
        x--; y--;
        g.add_edge(x,y);
    }
    g.decomposition();
    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 << g.solve(ms,K) << endl;
    }
}