Bình luận

• 
  

  0

  

  dragon3012009  đã bình luận lúc 11, Tháng 10, 2025, 9:56 ← sửa 2 →

  Link bài gốc : link

• 
  

  -1

  

  username001  đã bình luận lúc 11, Tháng 10, 2025, 7:49

  include <bits/stdc++.h>

  using namespace std;

  const long long MOD = 1'000'000'007LL; const int LOG = 19; // 2^18 = 262144 > 2·10⁵ const long long INV2 = (MOD + 1) / 2; // modular inverse of 2

  /----------------------------------------------------------------- Global data for the original tree -----------------------------------------------------------------/ int N, Q; vector<int> g[200005]; int tin[200005], tout[200005], timerDFS = 0; int depthNode[200005]; int up[200005][LOG]; // binary lifting table for LCA

  /----------------------------------------------------------------- DFS – Euler tour, depths and binary lifting -----------------------------------------------------------------/ void dfs(int v, int p) { tin[v] = ++timerDFS; up[v][0] = p; for (int i = 1; i < LOG; ++i) up[v][i] = up[ up[v][i-1] ][i-1];

  for (int to : g[v])
      if (to != p)
      {
          depthNode[to] = depthNode[v] + 1;
          dfs(to, v);
      }
  tout[v] = ++timerDFS;
  

  }

  /----------------------------------------------------------------- LCA utilities -----------------------------------------------------------------/ inline bool isancestor(int u, int v) // u is ancestor of v ? { return tin[u] <= tin[v] && tout[v] <= tout[u]; } int lca(int u, int v) { if (isancestor(u, v)) return u; if (isancestor(v, u)) return v; for (int i = LOG - 1; i >= 0; --i) if (!isancestor(up[u][i], v)) u = up[u][i]; return up[u][0]; }

  /----------------------------------------------------------------- Virtual tree (built only from the vertices of one query) -----------------------------------------------------------------/ struct VirtualTree { vector<int> vert; // vertices of the virtual tree (sorted by tin) vector child; // children indices inside vert vector<char> isOrig; // 1 if the vertex belongs to the original query set

  void build(const vector<int>& base)
  {
      vector<int> all = base;                // we will also insert needed LCAs
  
      // order by tin
      vector<int> ord = base;
      sort(ord.begin(), ord.end(),
           [](int a, int b){ return tin[a] < tin[b]; });
  
      for (size_t i = 0; i + 1 < ord.size(); ++i)
          all.push_back(lca(ord[i], ord[i + 1]));   // needed LCAs
  
      sort(all.begin(), all.end(),
           [](int a, int b){ return tin[a] < tin[b]; });
      all.erase(unique(all.begin(), all.end()), all.end());
  
      vert = all;                     // already sorted by tin
      int sz = (int)vert.size();
      child.assign(sz, {});
      isOrig.assign(sz, 0);
  
      unordered_map<int,int> pos;
      pos.reserve(sz * 2);
      for (int i = 0; i < sz; ++i) pos[ vert[i] ] = i;
  
      for (int v : base) isOrig[ pos[v] ] = 1;   // mark original vertices
  
      // connect vertices – linear stack algorithm
      vector<int> st;
      for (int i = 0; i < sz; ++i)
      {
          int v = vert[i];
          while (!st.empty() && !is_ancestor(vert[st.back()], v))
              st.pop_back();
  
          if (!st.empty())
              child[ st.back() ].push_back(i);   // edge parent → i
  
          st.push_back(i);
      }
  }
  
  /* return Σ_{u&lt;v} u·v·depth[lca(u,v)] (mod MOD) */
  long long computeLcaSum()
  {
      long long ans = 0;
      int sz = (int)vert.size();
      vector&lt;long long> subSum(sz, 0);   // Σ of original vertex numbers in the subtree
  
      for (int i = sz - 1; i >= 0; --i)   // reverse tin order → post‑order
      {
          long long total = 0;          // Σ subSum[child]
          long long sumSq = 0;          // Σ subSum[child]²
  
          for (int ch : child[i])
          {
              long long v = subSum[ch];
              total = (total + v) % MOD;
              sumSq = (sumSq + v * v) % MOD;
          }
  
          long long curDepth = depthNode[ vert[i] ] % MOD;
  
          // pairs taken from two different child sub‑trees
          long long cross = ( ( (total * total) % MOD - sumSq + MOD) % MOD ) * INV2 % MOD;
          long long add   = curDepth * cross % MOD;
  
          // pairs where one endpoint is the LCA itself (only if it belongs to S)
          if (isOrig[i])
              add = (add + curDepth * (vert[i] % MOD) % MOD * total) % MOD;
  
          ans = (ans + add) % MOD;
  
          long long self = isOrig[i] ? (vert[i] % MOD) : 0;
          subSum[i] = (self + total) % MOD;
      }
      return ans;          // Σ u·v·depth[lca(u,v)] (mod MOD)
  }
  

  };

  /----------------------------------------------------------------- Main -----------------------------------------------------------------/ int main() { ios::syncwithstdio(false); cin.tie(nullptr);

  /* read N and Q (first line) */
  cin >> N >> Q;
  
  /* read the tree */
  for (int i = 0; i < N - 1; ++i)
  {
      int u, v;  cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
  }
  
  /* preprocessing – depth, euler tour, binary lifting */
  depthNode[1] = 0;
  dfs(1, 1);
  
  /* answer the Q queries */
  while (Q--)
  {
      int K;  cin >> K;
      vector<int> S(K);
      for (int i = 0; i < K; ++i) cin >> S[i];
  
      if (K < 2) {                     // no unordered pair
          cout << 0 << '\n';
          continue;
      }
  
      /* ---- part A : Σ depth[u]·u·(A‑u) ---- */
      long long A = 0;                 // A = Σ x
      for (int x : S) A = (A + x) % MOD;
  
      long long termA = 0;
      for (int x : S)
      {
          long long d   = depthNode[x] % MOD;
          long long xi  = x % MOD;
          long long rest = (A - xi + MOD) % MOD;
          termA = (termA + d * xi % MOD * rest) % MOD;
      }
  
      /* ---- part B : L = Σ u·v·depth[lca(u,v)] ---- */
      VirtualTree vt;
      vt.build(S);
      long long L = vt.computeLcaSum();            // already modulo MOD
  
      long long termB = (2LL * L) % MOD;
      long long ans   = (termA - termB) % MOD;
      if (ans < 0) ans += MOD;
  
      cout << ans << '\n';
  }
  return 0;
  

  }