#386649 (C++14) No.900 aδδitivee

提出ソース
結果

問題	No.900 aδδitivee
コンテスト
ユーザー	lumc_
提出日時	2019-10-04 21:50:24
言語	C++14 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	164 ms / 2,000 ms
コード長	16,767 bytes
コンパイル時間	1,699 ms
コンパイル使用メモリ	145,884 KB
実行使用メモリ	27,452 KB
最終ジャッジ日時	2024-10-03 07:27:29
合計ジャッジ時間	6,616 ms
ジャッジサーバーID （参考情報）	judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 2
other	AC * 27
権限があれば一括ダウンロードができます
ソースコード

raw source code
// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
#include<bitset>
#include<cstdlib>
// #include<deque>
// #include<multiset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

// HLD( <tree> , root )
// === .build() ===
// .fold(hi, lo, func, inclusive)
//   where func(l, r) proceeds with [l, r)
// === O(1) ===
// .in(a) : in-time of Euler Tour : alias = .[a]
// .out(a) : out-time of Euler Tour
// .rev(a) : rev[in[a]] = a
// .head(a) : ascend all light edges
// .tail(a) : descend all heavy edges
// ---
// .subtree_size(a)
// .depth(a) : 0-indexed
// .parent(a) : -1 if [a] is root
// .heavy(a) : [a] cannot be a leaf. return the node opposite of the heavy edge
// === O(log n) ===
// .climb(a)
// .descendTo(from, to, steps)
// .steps(a, b)
// === --- ===
// for subtree : [ .in(a)           , .out(a) )
// (exclusive) : [ .in_exclusive(a) , .out(a) )
// HL-Decomposition {{{
#include <cassert>
#include <functional>
#include <vector>
// based on Euler Tour
struct HLD {
public:
  using size_type = std::size_t;
  using graph_type = std::vector< std::vector< int > >;

private:
  size_type n;
  std::vector< size_type > hd, tl;
  std::vector< size_type > sub;
  std::vector< size_type > dep;
  std::vector< int > par;
  std::vector< size_type > vid;
  size_type root;
  graph_type tree;

public:
  HLD() : n(0) {}
  HLD(size_type n, size_type root = 0)
    : n(n), hd(n), tl(n), sub(n), dep(n), par(n), vid(n), tree(n) {
      setRoot(root);
    }
  HLD(const graph_type &tree, size_type root) : HLD(tree.size(), root) {
    this->tree = tree;
  }

  void setRoot(size_type root) {
    assert(root < n);
    this->root = root;
  }

private:
  bool built = 0;
  std::vector< size_type > vid_rev;

public:
  void build() {
    assert(!built && n);
    built = 1;

    vid_rev.resize(n);

    hd[root] = root;
    dfs0();
    dfs1();
    for(size_type i = 0; i < n; i++) vid_rev[vid[i]] = i;
  }

private:
  void dfs0() {
    std::vector< int > used(n);
    std::vector< std::tuple< size_type, int, size_type > > stk;
    stk.reserve(n);
    stk.emplace_back(root, -1, 0);
    while(stk.size()) {
      size_type i, d;
      int p;
      std::tie(i, p, d) = stk.back();
      if(!used[i]) {
        used[i] = 1;
        par[i] = p;
        dep[i] = d;
        for(auto &j : tree[i])
          if(j != p) {
            stk.emplace_back(j, i, d + 1);
          }
      } else {
        stk.pop_back();
        sub[i] = 1;
        for(auto &j : tree[i])
          if(j != p) {
            if(sub[j] > sub[tree[i].back()]) {
              std::swap(tree[i].back(), j);
            }
            sub[i] += sub[j];
          }
        if(tree[i].back() != p) {
          tl[i] = tl[tree[i].back()];
        } else {
          tl[i] = i;
        }
      }
    }
  }
  void dfs1() {
    std::vector< int > used(n);
    std::vector< std::tuple< size_type, int > > stk;
    stk.reserve(n);
    stk.emplace_back(root, -1);
    size_type id = 0;
    while(stk.size()) {
      size_type i;
      int p;
      std::tie(i, p) = stk.back(), stk.pop_back();
      vid[i] = id++;
      for(auto j : tree[i])
        if(j != p) {
          hd[j] = j == tree[i].back() ? hd[i] : j;
          stk.emplace_back(j, i);
        }
    }
  }

public:
  size_type operator[](size_type i) const { return in(i); }
  size_type in(size_type i) const {
    assert(built);
    assert(i < n);
    return vid[i];
  }
  size_type in_exclusive(size_type i) const { return in(i) + 1; }
  size_type out(size_type i) const {
    assert(built);
    assert(i < n);
    return vid[i] + sub[i];
  }
  size_type out_exclusive(size_type i) const { return out(i) - 1; }
  size_type head(size_type i) const {
    assert(built);
    return hd.at(i);
  }
  size_type tail(size_type i) const {
    assert(built);
    return tl.at(i);
  }
  size_type rev(size_type i) const {
    assert(built);
    return vid_rev.at(i);
  }
  size_type subtree_size(size_type i) const {
    assert(built);
    return sub.at(i);
  }
  size_type depth(size_type i) const {
    assert(built);
    return dep.at(i);
  }
  int parent(size_type i) const {
    assert(built);
    return par.at(i);
  }
  size_type steps(size_type a, size_type b) const {
    assert(built);
    assert(a < n && b < n);
    return dep[a] + dep[b] - 2 * dep[lca(a, b)];
  }
  size_type climb(size_type a, long long t) const {
    assert(built);
    assert(a < n && t >= 0);
    while(t) {
      long long c = std::min< long long >(vid[a] - vid[hd[a]], t);
      t -= c;
      a = vid_rev[vid[a] - c];
      if(t && a != root) {
        t--;
        a = par[a];
      }
      if(a == root) break;
    }
    return a;
  }
  size_type descendTo(size_type from, size_type to, long long steps) const {
    assert(built);
    assert(steps >= 0);
    assert(from < n && to < n);
    return climb(to, dep[to] - dep[from] - steps);
  }
  void add_edge(size_type a, size_type b) {
    assert(!built);
    assert(a < n && b < n);
    tree[a].emplace_back(b);
    tree[b].emplace_back(a);
  }
  size_type lca(size_type a, size_type b) const {
    assert(built);
    assert(a < n && b < n);
    while(1) {
      if(vid[a] > vid[b]) std::swap(a, b);
      if(hd[a] == hd[b]) return a;
      b = par[hd[b]];
    }
  }
  size_type heavy(size_type a) const {
    assert(built);
    assert(a < n);
    assert(tree[a].back() != par[a]);
    return tree[a].back();
  }
  void fold(size_type hi, int lo, std::function< void(int, int) > f,
      bool inclusive) const {
    assert(built);
    assert(hi < n && 0 <= lo && lo < (int) n);
    while(lo != -1 && dep[lo] >= dep[hi]) {
      size_type nex = std::max(vid[hd[lo]], vid[hi]);
      f(nex + (nex == vid[hi] && !inclusive), vid[lo] + 1);
      lo = par[hd[lo]];
    }
  }
  size_type size() const { return n; }
};
// }}}

const int N = 1e5;
std::vector<std::vector<pair<int, int>>> g;
int n;

// LazySegmentTree( size [, initial] )
// LazySegmentTree( <data> )
/// --- LazySegmentTree {{{ ///
#include <cassert>
#include <initializer_list>
#include <iostream>
#include <vector>
template < class M_act >
struct LazySegmentTree {
public:
  using Monoid = typename M_act::Monoid;
  using X = typename Monoid::T;
  using M = typename M_act::M;

private:
  size_t n;
  int h;
  vector< X > data;
  vector< M > lazy;
  vector< size_t > nodeLength;
  // call before use data[i]
  void eval(size_t i) {
    if(lazy[i] == M_act::identity()) return;
    data[i] = M_act::actInto(lazy[i], nodeLength[i], data[i]);
    if(i < n) {
      lazy[i * 2] = M_act::op(lazy[i], lazy[i * 2]);
      lazy[i * 2 + 1] = M_act::op(lazy[i], lazy[i * 2 + 1]);
    }
    lazy[i] = M_act::identity();
  }
  // call before use seg[i] = data[i + n]
  void evalDown(size_t i) {
    i += n;
    for(int j = h - 1; j >= 0; j--) eval(i >> j);
  }
  // call after touch seg[i] = data[i + n]
  void propUp(size_t i) {
    i += n;
    while(i >>= 1)
      eval(i * 2), eval(i * 2 + 1), data[i] = Monoid::op(data[i * 2], data[i * 2 + 1]);
  }

public:
  LazySegmentTree() : n(0) {}
  LazySegmentTree(size_t n, X initial = Monoid::identity()) : n(n) {
    if(n > 0) {
      h = 1;
      while(1u << h < n) h++;
      data.resize(2 * n, initial);
      lazy.resize(2 * n, M_act::identity());
      nodeLength.resize(2 * n, 1);
      for(size_t i = n - 1; i > 0; i--) // fill from deep
        data[i] = Monoid::op(data[i * 2], data[i * 2 + 1]),
          nodeLength[i] = nodeLength[i * 2] + nodeLength[i * 2 + 1];
    }
  }
  template < class InputIter, class = typename iterator_traits< InputIter >::value_type >
    LazySegmentTree(InputIter first, InputIter last)
    : LazySegmentTree(distance(first, last)) {
      if(n > 0) {
        copy(first, last, begin(data) + n);
        for(size_t i = n - 1; i > 0; i--) // fill from deep
          data[i] = Monoid::op(data[i * 2], data[i * 2 + 1]);
      }
    }
  LazySegmentTree(vector< X > v) : LazySegmentTree(v.begin(), v.end()) {}
  LazySegmentTree(initializer_list< X > v) : LazySegmentTree(v.begin(), v.end()) {}
  void act(int l, int r, const M &m) {
    if(l < 0) l = 0;
    if(l >= r) return;
    if(r > (int) n) r = n;
    evalDown(l);
    evalDown(r - 1);
    int tl = l, tr = r;
    for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if(l & 1) eval(l), lazy[l] = m, eval(l), l++;
      if(r & 1) --r, eval(r), lazy[r] = m, eval(r);
    }
    propUp(tl);
    propUp(tr - 1);
  }
  void set(size_t i, const X &x) {
    assert(i < n);
    evalDown(i);
    data[i + n] = x;
    propUp(i);
  }
  X get(size_t i) {
    assert(i < n);
    evalDown(i);
    return data[i + n];
  }
  X fold(int l, int r) {
    if(l < 0) l = 0;
    if(l >= r) return Monoid::identity();
    if(r > (int) n) r = n;
    evalDown(l);
    evalDown(r - 1);
    X tmpL = Monoid::identity(), tmpR = Monoid::identity();
    for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if(l & 1) eval(l), tmpL = Monoid::op(tmpL, data[l]), l++;
      if(r & 1) --r, eval(r), tmpR = Monoid::op(data[r], tmpR);
    }
    return Monoid::op(tmpL, tmpR);
  }
  int size() { return n; }
  inline void dum(int r = -1) {
#ifdef DEBUG
    if(r < 0) r = n;
    DEBUG_OUT << "{";
    for(int i = 0; i < min(r, (int) n); i++) DEBUG_OUT << (i ? ", " : "") << get(i);
    DEBUG_OUT << "}" << endl;
#endif
  }
};

/// }}}--- ///

/// --- Monoid examples {{{ ///
constexpr long long inf_monoid = 1e18 + 100;
#include <algorithm>
struct Nothing {
  using T = char;
  using Monoid = Nothing;
  using M = T;
  static constexpr T op(const T &, const T &) { return T(); }
  static constexpr T identity() { return T(); }
  template < class X >
    static constexpr X actInto(const M &, long long, const X &x) {
      return x;
    }
};

template < class U = long long >
struct RangeMin {
  using T = U;
  static T op(const T &a, const T &b) { return std::min< T >(a, b); }
  static constexpr T identity() { return T(inf_monoid); }
};

template < class U = long long >
struct RangeMax {
  using T = U;
  static T op(const T &a, const T &b) { return std::max< T >(a, b); }
  static constexpr T identity() { return T(-inf_monoid); }
};

template < class U = long long >
struct RangeSum {
  using T = U;
  static T op(const T &a, const T &b) { return a + b; }
  static constexpr T identity() { return T(0); }
};

template < class U >
struct RangeProd {
  using T = U;
  static T op(const T &a, const T &b) { return a * b; }
  static constexpr T identity() { return T(1); }
};

template < class U = long long >
struct RangeOr {
  using T = U;
  static T op(const T &a, const T &b) { return a | b; }
  static constexpr T identity() { return T(0); }
};

#include <bitset>

template < class U = long long >
struct RangeAnd {
  using T = U;
  static T op(const T &a, const T &b) { return a & b; }
  static constexpr T identity() { return T(-1); }
};

template < size_t N >
struct RangeAnd< std::bitset< N > > {
  using T = std::bitset< N >;
  static T op(const T &a, const T &b) { return a & b; }
  static constexpr T identity() { return std::bitset< N >().set(); }
};

/// }}}--- ///

/// --- M_act examples {{{ ///
template < class U = long long, class V = U >
struct RangeMinAdd {
  using X = U;
  using M = V;
  using Monoid = RangeMin< U >;
  static M op(const M &a, const M &b) { return a + b; }
  static constexpr M identity() { return 0; }
  static X actInto(const M &m, long long, const X &x) { return m + x; }
};

template < class U = long long, class V = U >
struct RangeMaxAdd {
  using X = U;
  using M = V;
  using Monoid = RangeMax< U >;
  static M op(const M &a, const M &b) { return a + b; }
  static constexpr M identity() { return 0; }
  static X actInto(const M &m, long long, const X &x) { return m + x; }
};

template < class U = long long, class V = U >
struct RangeMinSet {
  using M = U;
  using Monoid = RangeMin< U >;
  using X = typename Monoid::T;
  static M op(const M &a, const M &b) { return a == identity() ? b : a; }
  static constexpr M identity() { return M(-inf_monoid); }
  static X actInto(const M &m, long long, const X &x) { return m == identity() ? x : m; }
};

template < class U = long long, class V = U >
struct RangeMaxSet {
  using M = U;
  using Monoid = RangeMax< U >;
  using X = typename Monoid::T;
  static M op(const M &a, const M &b) { return a == identity() ? b : a; }
  static constexpr M identity() { return M(-inf_monoid); }
  static X actInto(const M &m, long long, const X &x) { return m == identity() ? x : m; }
};

template < class U = long long, class V = U >
struct RangeSumAdd {
  using X = U;
  using M = V;
  using Monoid = RangeSum< U >;
  static M op(const M &a, const M &b) { return a + b; }
  static constexpr M identity() { return 0; }
  static X actInto(const M &m, long long n, const X &x) { return m * n + x; }
};

template < class U = long long, class V = U >
struct RangeSumSet {
  using X = U;
  using M = V;
  using Monoid = RangeSum< U >;
  static M op(const M &a, const M &b) { return a == identity() ? a : b; }
  static constexpr M identity() { return M(-inf_monoid); }
  static X actInto(const M &m, long long n, const X &x) {
    return m == identity() ? x : m * n;
  }
};

template < class U, class V = U >
struct RangeProdMul {
  using X = U;
  using M = V;
  using Monoid = RangeProd< U >;
  static M mpow(M a, long long b) {
    X r(1);
    while(b) {
      if(b & 1) r = r * a;
      a = a * a;
      b >>= 1;
    }
    return r;
  }
  static M op(const M &a, const M &b) { return a * b; }
  static constexpr M identity() { return M(1); }
  static X actInto(const M &m, long long n, const X &x) { return x * mpow(m, n); }
};

template < class U, class V = U >
struct RangeProdSet {
  using X = U;
  using M = V;
  using Monoid = RangeProd< U >;
  static M op(const M &a, const M &b) { return a == identity() ? b : a; }
  static constexpr M identity() { return V::unused; }
  static X actInto(const M &m, long long n, const X &) {
    if(m == identity()) return;
    return RangeProdMul< U, V >::mpow(m, n);
  }
};

template < class U = long long, class V = U >
struct RangeOrSet {
  using X = U;
  using M = V;
  using Monoid = RangeOr< U >;
  static M op(const M &a, const M &b) { return a == identity() ? b : a; }
  static constexpr M identity() { return M(-inf_monoid); }
  static X actInto(const M &m, long long, const X &x) { return m == identity() ? x : m; }
};

template < class U = long long, class V = U >
struct RangeAndSet {
  using X = U;
  using M = V;
  using Monoid = RangeAnd< U >;
  static M op(const M &a, const M &b) { return a == identity() ? b : a; }
  static constexpr M identity() { return M(-inf_monoid); }
  static X actInto(const M &m, long long, const X &x) { return m == identity() ? x : m; }
};

template < class U = long long, class V = U >
struct RangeOr2 {
  using X = U;
  using M = V;
  using Monoid = RangeOr< U >;
  static M op(const M &a, const M &b) { return a | b; }
  static constexpr M identity() { return M(0); }
  static X actInto(const M &m, long long, const X &x) { return m | x; }
};

template < class U = long long, class V = U >
struct RangeAnd2 {
  using X = U;
  using M = V;
  using Monoid = RangeAnd< U >;
  static M op(const M &a, const M &b) { return a & b; }
  static constexpr M identity() { return M(-1); }
  static X actInto(const M &m, long long, const X &x) { return m & x; }
};

template < class U, size_t N >
struct RangeAnd2< U, std::bitset< N > > {
  using X = U;
  using M = std::bitset< N >;
  using Monoid = RangeAnd< U >;
  static M op(const M &a, const M &b) { return a & b; }
  static constexpr M identity() { return std::bitset< N >().set(); }
  static X actInto(const M &m, long long, const X &x) { return m & x; }
};
/// }}}--- ///

using Seg = LazySegmentTree< RangeSumAdd<> >;


int val[N];

void dfs(int i, int p = -1) {
  for(auto to : g[i]) if(to.first != p) {
    int j, w;
    tie(j, w) = to;
    dfs(j, i);
    val[j] = w;
  }
}

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  cin >> n;
  g.resize(n);
  HLD hld(n);
  for(int i = 0; i < n - 1; i++) {
    int a, b, w; std::cin >> a >> b >> w;
    g[a].emplace_back(b, w);
    g[b].emplace_back(a, w);
    hld.add_edge(a, b);
  }
  dfs(0);

  hld.build();

  Seg seg(n);

  for(int i = 0; i < n; i++) seg.set(hld[i], val[i]);


  int q;
  cin >> q;
  for(int i = 0; i < q; i++) {
    int t;
    cin >> t;
    if(t == 1) {
      int a, x;
      cin >> a >> x;
      seg.act(hld.in_exclusive(a), hld.out(a), x);
    } else {
      int b;
      cin >> b;
      ll ans = 0;
      hld.fold(0, b, [&ans, &seg](int l, int r){
          ans += seg.fold(l, r);
          }, 0);
      cout << ans << "\n";
    }
  }
  return 0;
}
yukicoder

結果

ソースコード
