#727345 (C++17) No.1038 TreeAddQuery

• 問題: No.1038 TreeAddQuery
• ユーザー: maspy
• 提出日時: 2021-12-31 14:20:20
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 1,653 ms / 4,000 ms
• コード長: 14,211 bytes
• コンパイル時間: 5,536 ms
• コンパイル使用メモリ: 235,900 KB
• 実行使用メモリ: 29,224 KB
• 最終ジャッジ日時: 2024-04-17 02:07:22
• 合計ジャッジ時間: 27,233 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	11 ms; 5,376 KB
testcase_04	AC	12 ms; 5,376 KB
testcase_05	AC	10 ms; 5,376 KB
testcase_06	AC	12 ms; 5,376 KB
testcase_07	AC	13 ms; 5,376 KB
testcase_08	AC	984 ms; 24,804 KB
testcase_09	AC	1,081 ms; 25,728 KB
testcase_10	AC	1,060 ms; 24,932 KB
testcase_11	AC	1,058 ms; 24,924 KB
testcase_12	AC	1,114 ms; 25,768 KB
testcase_13	AC	1,653 ms; 25,556 KB
testcase_14	AC	1,344 ms; 25,684 KB
testcase_15	AC	1,279 ms; 25,692 KB
testcase_16	AC	1,161 ms; 25,776 KB
testcase_17	AC	1,120 ms; 25,552 KB
testcase_18	AC	251 ms; 29,224 KB
testcase_19	AC	285 ms; 25,320 KB
testcase_20	AC	278 ms; 24,844 KB
testcase_21	AC	337 ms; 24,548 KB
testcase_22	AC	453 ms; 24,552 KB
testcase_23	AC	512 ms; 24,776 KB
testcase_24	AC	829 ms; 25,776 KB
testcase_25	AC	1,401 ms; 25,556 KB
testcase_26	AC	852 ms; 27,588 KB

ソースコード

#line 1 "main.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1038"
#line 2 "/home/maspy/library/my_template.hpp"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ll8 = __int128;
using ld = long double;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using uint = unsigned int;
using ull = unsigned long long;

template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

#define vec(type, name, ...) vector<type> name(__VA_ARGS__)
#define VEC(type, name, size) \
  vector<type> name(size);    \
  IN(name)
#define vv(type, name, h, ...) \
  vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define VV(type, name, h, w)                     \
  vector<vector<type>> name(h, vector<type>(w)); \
  IN(name)
#define vvv(type, name, h, w, ...)   \
  vector<vector<vector<type>>> name( \
      h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...)       \
  vector<vector<vector<vector<type>>>> name( \
      a, vector<vector<vector<type>>>(       \
             b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))

#define FOR(i, n) for (ll i = 0; (i) < (ll)(n); ++(i))
#define FOR3(i, m, n) for (ll i = (m); (i) < (ll)(n); ++(i))
#define FOR_R(i, n) for (ll i = (ll)(n)-1; (i) >= 0; --(i))
#define FOR3_R(i, m, n) for (ll i = (ll)(n)-1; (i) >= (ll)(m); --(i))
#define FOR_subset(t, s) for (ll t = s; t >= 0; t = (t == 0 ? -1 : (t - 1) & s))
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if

#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second

int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(uint x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(ull x) { return __builtin_popcountll(x); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return 31 - __builtin_clz(x); }
int topbit(uint x) { return 31 - __builtin_clz(x); }
int topbit(ll x) { return 63 - __builtin_clzll(x); }
int topbit(ull x) { return 63 - __builtin_clzll(x); }
// (0, 1, 2, 3, 4) -> (32 or 64, 0, 1, 0, 2)
int lowbit(int x) { return 31 - __builtin_clz(x); }
int lowbit(uint x) { return 31 - __builtin_clz(x); }
int lowbit(ll x) { return 63 - __builtin_clzll(x); }
int lowbit(ull x) { return 63 - __builtin_clzll(x); }

ll ceil(ll x, ll y) { return (x > 0 ? (x + y - 1) / y : x / y); }
ll floor(ll x, ll y) { return (x > 0 ? x / y : (x - y + 1) / y); }
pi divmod(ll x, ll y) {
  ll q = floor(x, y);
  return {q, x - q * y};
}

#define INT(...)   \
  int __VA_ARGS__; \
  IN(__VA_ARGS__)
#define LL(...)   \
  ll __VA_ARGS__; \
  IN(__VA_ARGS__)
#define STR(...)      \
  string __VA_ARGS__; \
  IN(__VA_ARGS__)
#define CHR(...)    \
  char __VA_ARGS__; \
  IN(__VA_ARGS__)
#define DBL(...)           \
  long double __VA_ARGS__; \
  IN(__VA_ARGS__)
void scan(int &a) { cin >> a; }
void scan(long long &a) { cin >> a; }
void scan(char &a) { cin >> a; }
void scan(double &a) { cin >> a; }
void scan(long double &a) { cin >> a; }
void scan(string &a) { cin >> a; }
template <class T>
void scan(pair<T, T> &p) {
  scan(p.first), scan(p.second);
}
template <class T>
void scan(tuple<T, T, T> &p) {
  scan(get<0>(p)), scan(get<1>(p)), scan(get<2>(p));
}
template <class T>
void scan(tuple<T, T, T, T> &p) {
  scan(get<0>(p)), scan(get<1>(p)), scan(get<2>(p)), scan(get<3>(p));
}
template <class T>
void scan(vector<T> &a) {
  for (auto &i: a) scan(i);
}
template <class T>
void scan(T &a) {
  cin >> a;
}
void IN() {}
template <class Head, class... Tail>
void IN(Head &head, Tail &... tail) {
  scan(head);
  IN(tail...);
}

vi s_to_vi(string S, char first_char = 'a') {
  vi A(S.size());
  FOR(i, S.size()) { A[i] = S[i] - first_char; }
  return A;
}

template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &A) {
  os << A.fi << " " << A.se;
  return os;
}
template <typename T1, typename T2, typename T3>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &t) {
  os << get<0>(t) << " " << get<1>(t) << " " << get<2>(t);
  return os;
}
template <typename T1, typename T2, typename T3, typename T4>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3, T4> &t) {
  os << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << " " << get<3>(t);
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &A) {
  for (size_t i = 0; i < A.size(); i++) {
    if (i) os << " ";
    os << A[i];
  }
  return os;
}

void print() { cout << "\n"; }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
  cout << head;
  if (sizeof...(Tail)) cout << " ";
  print(forward<Tail>(tail)...);
}

void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void no(bool t = 1) { yes(!t); }

template <typename T>
vector<T> cumsum(vector<T> &A) {
  int N = A.size();
  vector<T> B(N + 1);
  B[0] = T(0);
  FOR(i, N) { B[i + 1] = B[i] + A[i]; }
  return B;
}

vc<int> bin_count(vi &A, int size) {
  vc<int> C(size);
  for (auto &x: A) { ++C[x]; }
  return C;
}

template <typename T>
vector<int> argsort(vector<T> &A) {
  vector<int> ids(A.size());
  iota(all(ids), 0);
  sort(all(ids),
       [&](int i, int j) { return A[i] < A[j] || (A[i] == A[j] && i < j); });
  return ids;
}

ll binary_search(function<bool(ll)> check, ll ok, ll ng) {
  assert(check(ok));
  while (abs(ok - ng) > 1) {
    auto x = (ng + ok) / 2;
    if (check(x))
      ok = x;
    else
      ng = x;
  }
  return ok;
}

template <class T, class S>
inline bool chmax(T &a, const S &b) {
  return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
  return (a > b ? a = b, 1 : 0);
}

#define SUM(v) accumulate(all(v), 0LL)
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end())
#line 3 "main.cpp"

#line 1 "/home/maspy/library/algebra/addgroup.hpp"
template <class X, X ZERO = X(0)>
struct AddGroup {
  using value_type = X;
  static constexpr X op(const X &x, const X &y) noexcept { return x + y; }
  static constexpr X inverse(const X &x) noexcept { return -x; }
  static constexpr X power(const X &x, ll n) noexcept { return n * x; }
  static constexpr X unit = ZERO;
  static constexpr bool commute = true;
};
#line 2 "/home/maspy/library/ds/fenwick.hpp"
template <typename AbelGroup>
struct FenwickTree {
  using E = typename AbelGroup::value_type;
  int n;
  vector<E> dat;
  E total;

  FenwickTree() : FenwickTree(0) {}
  FenwickTree(int n) : n(n), total(AbelGroup::unit) {
    assert(AbelGroup::commute);
    dat.assign(n, AbelGroup::unit);
  }
  FenwickTree(vc<E> v) : n(len(v)), total(AbelGroup::unit) {
    assert(AbelGroup::commute);
    dat = v;
    FOR3(i, 1, n + 1) {
      int j = i + (i & -i);
      if (j <= n) dat[j - 1] = AbelGroup::op(dat[i - 1], dat[j - 1]);
    }
  }

  E sum(int k) {
    E ret = AbelGroup::unit;
    for (; k > 0; k -= k & -k) ret = AbelGroup::op(ret, dat[k - 1]);
    return ret;
  }

  E sum(int L, int R) {
    E pos = AbelGroup::unit;
    while (L < R) {
      pos = AbelGroup::op(pos, dat[R - 1]);
      R -= R & -R;
    }
    E neg = AbelGroup::unit;
    while (R < L) {
      neg = AbelGroup::op(neg, dat[L - 1]);
      L -= L & -L;
    }
    return AbelGroup::op(pos, AbelGroup::inverse(neg));
  }

  E sum_all() { return total; }

  void add(int k, E x) {
    total = AbelGroup::op(total, x);
    for (++k; k <= n; k += k & -k) dat[k - 1] = AbelGroup::op(dat[k - 1], x);
  }

  template <class F>
  int max_right(F& check) {
    assert(f(E(0)));
    ll i = 0;
    E s = AbelGroup::unit;
    int k = 1;
    int N = len(dat) + 1;
    while (2 * k < N) k *= 2;
    while (k) {
      if (i + k < N && check(AbelGroup::op(s, dat[i + k - 1]))) {
        i += k;
        s = AbelGroup::op(s, dat[i - 1]);
      }
      k >>= 1;
    }
    return i;
  }

  int find_kth_element(E k) {
    auto check = [&](E x) -> bool { return x < k; };
    return max_right(check);
  }

  void debug() { print("fenwick", dat); }
};
#line 2 "/home/maspy/library/graph/base.hpp"

template <typename T>
struct Edge {
  int frm, to;
  T cost;
  int id;
};

template <typename T, bool directed = false>
struct Graph {
  int N, M;
  using cost_type = T;
  using edge_type = Edge<T>;
  vector<edge_type> edges;
  vector<int> indptr;
  vector<edge_type> csr_edges;
  bool prepared;

  class OutgoingEdges {
  public:
    OutgoingEdges(const Graph* G, int l, int r) : G(G), l(l), r(r) {}

    const edge_type* begin() const {
      if (l == r) { return 0; }
      return &G->csr_edges[l];
    }

    const edge_type* end() const {
      if (l == r) { return 0; }
      return &G->csr_edges[r];
    }

  private:
    int l, r;
    const Graph* G;
  };

  bool is_prepared() { return prepared; }
  constexpr bool is_directed() { return directed; }

  Graph() {}
  Graph(int N) : N(N), M(0), prepared(0) {}

  void add(int frm, int to, T cost = 1, int i = -1) {
    assert(!prepared);
    assert(0 <= frm && frm < N && 0 <= to && to < N);
    if (i == -1) i = M;
    auto e = edge_type({frm, to, cost, i});
    edges.eb(e);
    ++M;
  }

  void prepare() {
    assert(!prepared);
    prepared = true;
    indptr.assign(N + 1, 0);
    for (auto&& e: edges) {
      indptr[e.frm + 1]++;
      if (!directed) indptr[e.to + 1]++;
    }
    FOR(v, N) indptr[v + 1] += indptr[v];
    auto counter = indptr;
    csr_edges.resize(indptr.back() + 1);
    for (auto&& e: edges) {
      csr_edges[counter[e.frm]++] = e;
      if (!directed)
        csr_edges[counter[e.to]++] = edge_type({e.to, e.frm, e.cost, e.id});
    }
  }

  OutgoingEdges operator[](int v) const {
    assert(prepared);
    return {this, indptr[v], indptr[v + 1]};
  }

  void debug() {
    print("Graph");
    if (!prepared) {
      print("frm to cost id");
      for (auto&& e: edges) print(e.frm, e.to, e.cost, e.id);
    } else {
      print("indptr", indptr);
      print("frm to cost id");
      FOR(v, N) for (auto&& e: (*this)[v]) print(e.frm, e.to, e.cost, e.id);
    }
  }

  int size() { return N; }
};
#line 2 "/home/maspy/library/graph/centroid.hpp"
template <typename Graph, typename E = int>
struct CentroidDecomposition {
  using edge_type = typename Graph::edge_type;
  using F = function<E(E, edge_type)>;
  Graph& G;
  F f; // (E path value, edge e) -> E new_path_value
  int N;
  vector<int> cdep; // depth in centroid tree
  vc<int> sz;
  vc<int> par;

  CentroidDecomposition(
      Graph& G, F f = [](int x, edge_type e) { return x + e.cost; })
      : G(G), N(G.N), f(f), sz(G.N), par(G.N), cdep(G.N, -1) {
    build();
  }

  int find(int v) {
    vc<int> V = {v};
    par[v] = -1;
    int p = 0;
    while (p < len(V)) {
      int v = V[p++];
      sz[v] = 0;
      for (auto&& e: G[v]) {
        if (e.to == par[v] || cdep[e.to] != -1) continue;
        par[e.to] = v;
        V.eb(e.to);
      }
    }
    while (len(V)) {
      int v = V.back();
      V.pop_back();
      sz[v] += 1;
      if (p - sz[v] <= p / 2) return v;
      sz[par[v]] += sz[v];
    }
    return -1;
  }

  void build() {
    assert(G.is_prepared());
    assert(!G.is_directed());
    int N = G.N;

    vc<pair<int, int>> st = {{0, 0}};
    while (len(st)) {
      auto [lv, v] = st.back();
      st.pop_back();
      auto c = find(v);
      cdep[c] = lv;
      for (auto&& [frm, to, cost, id]: G[c]) {
        if (cdep[to] == -1) st.eb(lv + 1, to);
      }
    }
  }

  vc<vc<pair<int, E>>> collect(int root, E root_val) {
    /*
    root を重心とする木において、(v, path data v) の vector を、方向ごとに集めて返す
    ・0 番目：root からのパスすべて（root を含む）
    ・i 番目：i 番目の方向
    */
    vc<vc<pair<int, E>>> res = {{{root, root_val}}};
    for (auto&& e: G[root]) {
      int nxt = e.to;
      if (cdep[nxt] < cdep[root]) continue;
      vc<pair<int, E>> dat;
      int p = 0;
      dat.eb(nxt, f(root_val, e));
      par[nxt] = root;
      while (p < len(dat)) {
        auto [v, val] = dat[p++];
        for (auto&& e: G[v]) {
          if (e.to == par[v]) continue;
          if (cdep[e.to] < cdep[root]) continue;
          par[e.to] = v;
          dat.eb(e.to, f(val, e));
        }
      }
      res.eb(dat);
      res[0].insert(res[0].end(), all(dat));
    }
    return res;
  }
};
#line 7 "main.cpp"

void solve() {
  LL(N, Q);
  Graph<int> G(N);
  FOR(_, N - 1) {
    LL(a, b);
    G.add(--a, --b);
  }
  G.prepare();

  using T = tuple<ll, ll, ll>;
  VEC(T, query, Q);
  for (auto&& [a, b, c]: query) --a;

  // 頂点 -> クエリ
  vc<vi> query_at(N);
  FOR(q, Q) query_at[get<0>(query[q])].eb(q);

  CentroidDecomposition CD(G);
  vi ANS(Q);
  FenwickTree<AddGroup<ll>> bit(N + 10);

  FOR(root, N) {
    auto dats = CD.collect(root, 0);
    FOR(i, len(dats)) {
      auto dat = dats[i];
      // qid, v, dv
      vc<T> event;
      for (auto&& [v, dv]: dat) {
        for (auto&& q: query_at[v]) { event.eb(q, v, dv); }
      }
      sort(all(event));
      for (auto&& [qid, v, dv]: event) {
        auto [_, y, z] = query[qid];
        ll add = bit.sum(0, dv + 1);
        ANS[qid] += (i == 0 ? add : -add);
        if (dv <= y) {
          bit.add(0, z);
          bit.add(y - dv + 1, -z);
        }
      }
      for (auto&& [qid, v, dv]: event) {
        auto [_, y, z] = query[qid];
        if (dv <= y) {
          bit.add(0, -z);
          bit.add(y - dv + 1, +z);
        }
      }
    }
  }
  for (auto&& x: ANS) print(x);
}

signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << setprecision(15);

  ll T = 1;
  // LL(T);
  FOR(_, T) solve();

  return 0;
}