結果

問題 No.901 K-ary εxtrεεmε
ユーザー kusaf_
提出日時 2025-06-30 13:23:41
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 178 ms / 3,000 ms
コード長 7,163 bytes
コンパイル時間 4,349 ms
コンパイル使用メモリ 322,452 KB
実行使用メモリ 36,252 KB
最終ジャッジ日時 2025-06-30 13:23:55
合計ジャッジ時間 11,300 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;



struct Tree : vector<vector<ll>> {
  using vector<vector<ll>>::operator=;

 private:
  void dfs_sz(int v, int p) {
    sz[v] = 1;
    ord.emplace_back(v);
    for(int i = p, x = 0; i != -1;) {
      bl[v][x] = i;
      i = bl[i][x], x++;
    }
    for(auto &nv : (*this)[v]) {
      if(nv == p) {
        if((int)(*this)[v].size() >= 2 && nv == (*this)[v][0]) { std::swap((*this)[v][0], (*this)[v][1]); }
        else { continue; }
      }
      dp[nv] = dp[v] + 1;
      dfs_sz(nv, v);
      sz[v] += sz[nv];
      if(sz[nv] > sz[(*this)[v][0]]) { std::swap(nv, (*this)[v][0]); }
    }
  }
  void dfs_hld(int v) {
    down[v] = id++;
    for(auto &nv : (*this)[v]) {
      if(nv == parent(v)) { continue; }
      nx[nv] = (nv == (*this)[v][0] ? nx[v] : nv);
      dfs_hld(nv);
    }
    up[v] = id;
  }
  vector<pair<int, int>> ascend(int u, int v) const {
    vector<pair<int, int>> r;
    while(nx[u] != nx[v]) {
      r.emplace_back(down[u], down[nx[u]]);
      u = parent(nx[u]);
    }
    if(u != v) { r.emplace_back(down[u], down[v] + 1); }
    return r;
  }
  vector<pair<int, int>> descend(int u, int v) const {
    if(u == v) { return {}; }
    if(nx[u] == nx[v]) { return {{down[u] + 1, down[v]}}; }
    auto r = descend(u, parent(nx[v]));
    r.emplace_back(down[nx[v]], down[v]);
    return r;
  }

 public:
  int n, root, id = 0;
  vector<array<int, 24>> bl;
  vector<int> dp, sz, ord, down, up, nx;
  Tree(int n_, int r = 0): n(n_), root(r) { this->resize(n); }
  Tree(const vector<vector<ll>> &g, int r = 0): n(g.size()), root(r) {
    *this = g;
    build();
  }
  void add_edge(int u, int v) {
    (*this)[u].emplace_back(v);
    (*this)[v].emplace_back(u);
  }
  void build() {
    bl.resize(n);
    dp.resize(n);
    sz.resize(n);
    down.assign(n, -1);
    up.assign(n, -1);
    nx.assign(n, root);
    for(auto &v : bl) { ranges::fill(v, -1); }
    dfs_sz(root, -1);
    dfs_hld(root);
  }
  int size() const { return n; }
  int depth(int i) const { return dp[i]; }
  int parent(int i) const { return i == root ? root : bl[i][0]; }
  int order(int i) const { return ord[i]; }
  int in(int i) const { return down[i]; }
  int out(int i) const { return up[i]; }
  int size(int i) const { return sz[i]; }
  int kth_ancestor(int i, int k) const {
    if(dp[i] < k) { return -1; }
    while(k) {
      int t = __builtin_ctz(k);
      i = bl[i][t], k ^= 1 << t;
    }
    return i;
  }
  int distance(int u, int v) { return dp[u] + dp[v] - dp[lca(u, v)] * 2; }
  bool onpath(int u, int x, int v) { return distance(u, v) == distance(u, x) + distance(x, v); }
  int nxt(int u, int v) const {
    if(dp[u] >= dp[v]) { return parent(u); }
    int x = kth_ancestor(v, dp[v] - dp[u] - 1);
    return bl[x][0] == u ? x : bl[u][0];
  }
  vector<int> path(int u, int v) const {
    vector<int> pre, suf;
    while(dp[u] > dp[v]) {
      pre.emplace_back(u);
      u = bl[u][0];
    }
    while(dp[u] < dp[v]) {
      suf.emplace_back(v);
      v = bl[v][0];
    }
    while(u != v) {
      pre.emplace_back(u);
      suf.emplace_back(v);
      u = bl[u][0];
      v = bl[v][0];
    }
    pre.emplace_back(u);
    ranges::reverse(suf);
    copy(suf.begin(), suf.end(), back_inserter(pre));
    return pre;
  }
  int lca(int u, int v) {
    while(nx[u] != nx[v]) {
      if(down[u] < down[v]) { std::swap(u, v); }
      u = parent(nx[u]);
    }
    return dp[u] < dp[v] ? u : v;
  }
  int jump(int u, int v, int x) {
    int lc = lca(u, v), d1 = dp[u] - dp[lc];
    if(x <= d1) { return kth_ancestor(u, x); }
    int d = d1 + dp[v] - dp[lc];
    if(x <= d) { return kth_ancestor(v, d - x); }
    return -1;
  }
  vector<int> diameter() {
    int s = ranges::max_element(dp) - dp.begin();
    vector<int> d(n, -1);
    d[s] = 0;
    queue<int> q;
    q.emplace(s);
    while(!q.empty()) {
      int v = q.front();
      q.pop();
      for(auto &nv : (*this)[v]) {
        if(d[nv] == -1) {
          d[nv] = d[v] + 1;
          q.emplace(nv);
        }
      }
    }
    int t = ranges::max_element(d) - d.begin();
    return path(t, s);
  }
  template<typename F> void query(int u, int v, bool vertex, const F &f) {
    int l = lca(u, v);
    for(auto &&[a, b] : ascend(u, l)) {
      int s = a + 1, t = b;
      s > t ? f(t, s) : f(s, t);
    }
    if(vertex) f(down[l], down[l] + 1);
    for(auto &&[a, b] : descend(l, v)) {
      int s = a, t = b + 1;
      s > t ? f(t, s) : f(s, t);
    }
  }
  template<typename F> void noncommutative_query(int u, int v, bool vertex, const F &f) {
    int l = lca(u, v);
    for(auto &&[a, b] : ascend(u, l)) { f(a + 1, b); }
    if(vertex) { f(down[l], down[l] + 1); }
    for(auto &&[a, b] : descend(l, v)) { f(a, b + 1); }
  }
  template<typename F> void subtree_query(int u, bool vertex, const F &f) {
    f(down[u] + int(!vertex), up[u]);
  }
};

struct AuxiliaryTree : Tree {
  vector<vector<ll>> g;
  vector<ll> id, inv;
  AuxiliaryTree(const vector<vector<ll>> &g, ll r = 0): Tree(g, r), inv(g.size()) {}
  int build(const vector<ll> &v) {
    int N = v.size();
    g.assign(N, vector<ll>());
    id = v;
    ranges::sort(id, [&](auto x, auto y) { return (*this).in(x) < (*this).in(y); });
    stack<int> s;
    s.emplace(id[0]);
    inv[id[0]] = 0;
    for(int i = 0; i < N - 1; i++) {
      int u = (*this).lca(id[i], id[i + 1]);
      if(u != id[i]) {
        int p = inv[s.top()];
        while(true) {
          s.pop();
          if(s.empty() || (*this).depth(u) >= (*this).depth(s.top())) { break; }
          int tmp = inv[s.top()];
          g[tmp].emplace_back(p);
          p = tmp;
        }
        if(s.empty() || s.top() != u) {
          s.emplace(u);
          id.emplace_back(u);
          inv[u] = g.size();
          g.push_back({p});
        }
        else { g[inv[u]].emplace_back(p); }
      }
      s.emplace(id[i + 1]);
      inv[id[i + 1]] = i + 1;
    }
    int p = ((s.size() > 1) ? inv[s.top()] : -1);
    while(s.size() > 1) {
      s.pop();
      int tmp = inv[s.top()];
      g[tmp].emplace_back(p);
      p = tmp;
    }
    return inv[s.top()];
  }
  ll size() { return g.size(); }
  inline vector<ll> operator[](ll i) { return g[i]; }
  inline ll operator()(ll i) { return id[i]; }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll N;
  cin >> N;

  vector<tuple<ll, ll, ll>> e(N - 1);
  vector<vector<ll>> g(N);
  for(auto &[u, v, w] : e) {
    cin >> u >> v >> w;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }

  AuxiliaryTree t(g);

  vector<ll> S(N + 1, 0);
  for(auto &[u, v, w] : e) {
    if(t.depth(u) > t.depth(v)) { swap(u, v); }
    S[t.in(v) + 1] += w;
  }
  for(ll i = 0; i < N; i++) { S[i + 1] += S[i]; }

  ll Q;
  cin >> Q;
  while(Q--) {
    ll n;
    cin >> n;

    vector<ll> v(n);
    for(auto &i : v) { cin >> i; }
    ll r = t.build(v);

    ll ans = 0;
    auto DFS = [&](auto &&DFS, ll v, ll p = -1) -> void {
      if(p != -1) {
        t.query(t(p), t(v), false, [&](ll l, ll r) { ans += S[r] - S[l]; });
      }
      for(auto &nv : t[v]) {
        if(nv != p) { DFS(DFS, nv, v); }
      }
    };
    DFS(DFS, r);

    cout << ans << "\n";
  }
}
0