Submission #59471323

---

Source Code Expand

#include<bits/stdc++.h>
#include"atcoder/all"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef vector<ll> vi;
typedef pair<int,int> P;
constexpr ll mod = 998244353;
typedef modint998244353 mi;

struct S{
    long long val,idx;
};
S op(S x,S y){
    if(x.val>y.val)return y;
    return x;
}
S e() {
    return {LLONG_MAX,-1};
}

struct LCA{
    int N;
    vector<int>vs,depth,id,id_depth;
    vector<vector<int>> G;
    segtree<S,op,e> seg;

    LCA(int n,vector<vector<int>>&g){
        N=n;
        G=g;
        vs.resize(2*N-1);//DFSでの訪問順
        depth.resize(2*N-1);// 訪問順での根からの深さ
        id.resize(N); //id[i]:iが初めて現れるindex
        id_depth.resize(N);
        seg=segtree<S,op,e>(2*N-1);
        int k=0;
        dfs(0,-1,0,k);
        rep(i,2*N-1){
            seg.set(i,{depth[i],i});
        }
    }

    int lca(int u,int v){
        return vs[seg.prod(min(id[u],id[v]),max(id[u],id[v])+1).idx];
    }

    void dfs(int now,int par,int d,int& k){
        id[now]=k;
        id_depth[now]=d;
        vs[k]=now;
        depth[k++]=d;
        for(auto e:G[now]){
            if(e==par)continue;
            dfs(e,now,d+1,k);
            vs[k]=now;
            depth[k++]=d;
        }
    }
};

int main(){
    int n;cin>>n;
    vector<vector<int>>G(n);
    rep(i,n-1){
        int a,b;
        cin>>a>>b;
        a--;b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    LCA LCA(n,G);

    int q;cin>>q;
    rep(Q,q){
        int K;cin>>K;
        vector<P>V(K);
        rep(i,K){
            int v;cin>>v;v--;
            V[i]={LCA.id[v],v};
        }
        sort(all(V));
        V.push_back(V[0]);
        long long sum=0;
        rep(i,K){
            int w=LCA.lca(V[i].second,V[i+1].second);
            sum+=LCA.id_depth[V[i].second]+LCA.id_depth[V[i+1].second]-2*LCA.id_depth[w];
        }
        sum/=2;
        cout<<sum<<endl;
    }
}

Submission Info

Judge Result