LCCVjj - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
using ll = long long;

int N,Q,LOG;
vector<vector<int>> up;
vector<int> depth, tin, tout;
vector<vector<int>> g;
int timer=0;

void dfs0(int u, int p){
    tin[u]=++timer;
    up[0][u]= (p==-1 ? u : p);
    for(int k=1;k<LOG;k++) up[k][u]=up[k-1][ up[k-1][u] ];
    for(int v: g[u]) if(v!=p){
        depth[v]=depth[u]+1;
        dfs0(v,u);
    }
    tout[u]=timer;
}
bool is_anc(int u,int v){
    return tin[u]<=tin[v] && tout[v]<=tout[u];
}
int lca(int u,int v){
    if(is_anc(u,v)) return u;
    if(is_anc(v,u)) return v;
    for(int k=LOG-1;k>=0;k--){
        int x=up[k][u];
        if(!is_anc(x,v)) u=x;
    }
    return up[0][u];
}
int dist(int u,int v){ return depth[u]+depth[v]-2*depth[lca(u,v)]; }

vector<vector<pair<int,int>>> vt;
vector<int> used, inS;
ll dfs_sum(int u){
    ll s = inS[u]? u:0;
    for(auto [v,w]: vt[u]){
        ll sub = dfs_sum(v);
        s += sub;
    }
    return s;
}
ll dfs_ans(int u, ll tot, ll &ans){
    ll s = inS[u]? u:0;
    for(auto [v,w]: vt[u]){
        ll sub = dfs_ans(v, tot, ans);
        ans = (ans + (ll)w % MOD * (sub%MOD) % MOD * ((tot - sub)%MOD + MOD) % MOD) % MOD;
        s += sub;
    }
    return s;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>N>>Q;
    g.assign(N+1,{});
    for(int i=0;i<N-1;i++){
        int u,v; cin>>u>>v;
        g[u].push_back(v); g[v].push_back(u);
    }
    LOG = 1; while((1<<LOG) <= N) LOG++;
    up.assign(LOG, vector<int>(N+1));
    depth.assign(N+1,0);
    tin.assign(N+1,0); tout.assign(N+1,0);
    dfs0(1,-1);

    vt.assign(N+1,{});
    used.assign(N+1,0);
    inS.assign(N+1,0);

    while(Q--){
        int K; cin>>K;
        vector<int> a(K);
        for(int i=0;i<K;i++) cin>>a[i];
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end());
        K = (int)a.size();
        ll totSum = 0;
        for(int x: a){ inS[x]=1; totSum += x; }

        vector<int> vtx = a;
        sort(vtx.begin(), vtx.end(), [&](int x,int y){ return tin[x]<tin[y]; });
        int m = vtx.size();
        for(int i=0;i<m-1;i++) vtx.push_back(lca(vtx[i], vtx[i+1]));
        sort(vtx.begin(), vtx.end(), [&](int x,int y){ return tin[x]<tin[y]; });
        vtx.erase(unique(vtx.begin(), vtx.end()), vtx.end());

        for(int x: vtx) vt[x].clear();

        auto getLen = [&](int u,int v){ return dist(u,v); };
        vector<int> st;
        st.push_back(vtx[0]);
        for(size_t i=1;i<vtx.size();i++){
            int x = vtx[i];
            while(!st.empty() && !is_anc(st.back(), x)){
                int child = st.back(); st.pop_back();
                int parent = st.back();
                int w = getLen(parent, child);
                vt[parent].push_back({child, w});
            }
            if(st.empty() || st.back()!=x) st.push_back(x);
        }
        while(st.size()>1){
            int child = st.back(); st.pop_back();
            int parent = st.back();
            int w = getLen(parent, child);
            vt[parent].push_back({child, w});
        }
        int root = st[0];

        ll ans=0;
        dfs_ans(root, totSum%MOD, ans);
        cout<< (ans%MOD+MOD)%MOD << "\n";

        for(int x: a) inS[x]=0;
    }
    return 0;
}