#553629 (C++17) No.235 めぐるはめぐる (5)

提出ソース
結果

問題	No.235 めぐるはめぐる (5)
ユーザー	Haar
提出日時	2020-09-16 16:10:54
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,205 ms / 10,000 ms
コード長	13,374 bytes
コンパイル時間	3,432 ms
コンパイル使用メモリ	238,808 KB
実行使用メモリ	39,304 KB
最終ジャッジ日時	2024-06-22 03:19:52
合計ジャッジ時間	9,225 ms
ジャッジサーバーID （参考情報）	judge1 / judge3
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,205 ms 39,064 KB
testcase_01	AC	761 ms 39,280 KB
testcase_02	AC	1,087 ms 39,304 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>

#ifdef DEBUG
#include <Mylib/Debug/debug.cpp>
#else
#define dump(...) ((void)0)
#endif

template <typename T, typename U>
bool chmin(T &a, const U &b){
  return (a > b ? a = b, true : false);
}

template <typename T, typename U>
bool chmax(T &a, const U &b){
  return (a < b ? a = b, true : false);
}

template <typename T, size_t N, typename U>
void fill_array(T (&a)[N], const U &v){
  std::fill((U*)a, (U*)(a + N), v);
}

template <typename T, size_t N, size_t I = N>
auto make_vector(const std::array<int, N> &a, T value = T()){
  static_assert(I >= 1);
  static_assert(N >= 1);
  if constexpr (I == 1){
    return std::vector<T>(a[N - I], value);
  }else{
    return std::vector(a[N - I], make_vector<T, N, I - 1>(a, value));
  }
}

template <typename T>
std::ostream& operator<<(std::ostream &s, const std::vector<T> &a){
  for(auto it = a.begin(); it != a.end(); ++it){
    if(it != a.begin()) s << " ";
    s << *it;
  }
  return s;
}

template <typename T>
std::istream& operator>>(std::istream &s, std::vector<T> &a){
  for(auto &x : a) s >> x;
  return s;
}


/**
 * @title Modint
 * @docs mint.md
 */
namespace haar_lib {
  template <int32_t M>
  class modint {
    constexpr static int32_t MOD = M;
    uint32_t val;

  public:
    constexpr static auto mod(){return MOD;}

    constexpr modint(): val(0){}
    constexpr modint(int64_t n){
      if(n >= M) val = n % M;
      else if(n < 0) val = n % M + M;
      else val = n;
    }

    constexpr auto& operator=(const modint &a){val = a.val; return *this;}
    constexpr auto& operator+=(const modint &a){
      if(val + a.val >= M) val = (uint64_t)val + a.val - M;
      else val += a.val;
      return *this;
    }
    constexpr auto& operator-=(const modint &a){
      if(val < a.val) val += M;
      val -= a.val;
      return *this;
    }
    constexpr auto& operator*=(const modint &a){
      val = (uint64_t)val * a.val % M;
      return *this;
    }
    constexpr auto& operator/=(const modint &a){
      val = (uint64_t)val * a.inv().val % M;
      return *this;
    }

    constexpr auto operator+(const modint &a) const {return modint(*this) += a;}
    constexpr auto operator-(const modint &a) const {return modint(*this) -= a;}
    constexpr auto operator*(const modint &a) const {return modint(*this) *= a;}
    constexpr auto operator/(const modint &a) const {return modint(*this) /= a;}

    constexpr bool operator==(const modint &a) const {return val == a.val;}
    constexpr bool operator!=(const modint &a) const {return val != a.val;}

    constexpr auto& operator++(){*this += 1; return *this;}
    constexpr auto& operator--(){*this -= 1; return *this;}

    constexpr auto operator++(int){auto t = *this; *this += 1; return t;}
    constexpr auto operator--(int){auto t = *this; *this -= 1; return t;}

    constexpr static modint pow(int64_t n, int64_t p){
      if(p < 0) return pow(n, -p).inv();

      int64_t ret = 1, e = n % M;
      for(; p; (e *= e) %= M, p >>= 1) if(p & 1) (ret *= e) %= M;
      return ret;
    }

    constexpr static modint inv(int64_t a){
      int64_t b = M, u = 1, v = 0;

      while(b){
        int64_t t = a / b;
        a -= t * b; std::swap(a, b);
        u -= t * v; std::swap(u, v);
      }

      u %= M;
      if(u < 0) u += M;

      return u;
    }

    constexpr static auto frac(int64_t a, int64_t b){return modint(a) / modint(b);}

    constexpr auto pow(int64_t p) const {return pow(val, p);}
    constexpr auto inv() const {return inv(val);}

    friend constexpr auto operator-(const modint &a){return modint(M - a.val);}

    friend constexpr auto operator+(int64_t a, const modint &b){return modint(a) + b;}
    friend constexpr auto operator-(int64_t a, const modint &b){return modint(a) - b;}
    friend constexpr auto operator*(int64_t a, const modint &b){return modint(a) * b;}
    friend constexpr auto operator/(int64_t a, const modint &b){return modint(a) / b;}

    friend std::istream& operator>>(std::istream &s, modint<M> &a){s >> a.val; return s;}
    friend std::ostream& operator<<(std::ostream &s, const modint<M> &a){s << a.val; return s;}

    template <int N>
    static auto div(){
      static auto value = inv(N);
      return value;
    }

    explicit operator int32_t() const noexcept {return val;}
    explicit operator int64_t() const noexcept {return val;}
  };
}

/**
 * @title Basic graph
 * @docs graph.md
 */
namespace haar_lib {
  template <typename T>
  struct edge {
    int from, to;
    T cost;
    int index = -1;
    edge(){}
    edge(int from, int to, T cost): from(from), to(to), cost(cost){}
    edge(int from, int to, T cost, int index): from(from), to(to), cost(cost), index(index){}
  };

  template <typename T>
  struct graph {
    using weight_type = T;
    using edge_type = edge<T>;

    std::vector<std::vector<edge<T>>> data;

    auto& operator[](size_t i){return data[i];}
    const auto& operator[](size_t i) const {return data[i];}

    auto begin() const {return data.begin();}
    auto end() const {return data.end();}

    graph(){}
    graph(int N): data(N){}

    bool empty() const {return data.empty();}
    int size() const {return data.size();}

    void add_edge(int i, int j, T w, int index = -1){
      data[i].emplace_back(i, j, w, index);
    }

    void add_undirected(int i, int j, T w, int index = -1){
      add_edge(i, j, w, index);
      add_edge(j, i, w, index);
    }

    template <size_t I, bool DIRECTED = true, bool WEIGHTED = true>
    void read(int M){
      for(int i = 0; i < M; ++i){
        int u, v; std::cin >> u >> v;
        u -= I;
        v -= I;
        T w = 1;
        if(WEIGHTED) std::cin >> w;
        if(DIRECTED) add_edge(u, v, w, i);
        else add_undirected(u, v, w, i);
      }
    }
  };

  template <typename T>
  using tree = graph<T>;
}


/**
 * @title Heavy-light decomposition
 * @docs heavy_light_decomposition.md
 */
namespace haar_lib {
  template <typename T>
  class hl_decomposition {
    int n;

    std::vector<int> sub, // subtree size
      par, // parent id
      head, // chain head id
      id, // id[original id] = hld id
      rid, // rid[hld id] = original id
      next, // next node in a chain
      end; //

    int dfs_sub(tree<T> &tr, int cur, int p){
      par[cur] = p;
      int t = 0;
      for(auto &e : tr[cur]){
        if(e.to == p) continue;
        sub[cur] += dfs_sub(tr, e.to, cur);
        if(sub[e.to] > t){
          t = sub[e.to];
          next[cur] = e.to;
          std::swap(e, tr[cur][0]);
        }
      }
      return sub[cur];
    }

    void dfs_build(const tree<T> &tr, int cur, int &i){
      id[cur] = i;
      rid[i] = cur;
      ++i;

      for(auto &e : tr[cur]){
        if(e.to == par[cur]) continue;
        head[e.to] = (e.to == tr[cur][0].to ? head[cur] : e.to);
        dfs_build(tr, e.to, i);
      }

      end[cur] = i;
    }

  public:
    hl_decomposition(tree<T> tr, int root):
      n(tr.size()), sub(n, 1), par(n, -1), head(n), id(n), rid(n), next(n, -1), end(n, -1){
      dfs_sub(tr, root, -1);
      int i = 0;
      dfs_build(tr, root, i);
    }

    std::vector<std::tuple<int, int, bool>> path_query_vertex(int x, int y) const {
      std::vector<std::tuple<int, int, bool>> ret;
      const int w = lca(x, y);

      {
        int y = w;
        bool d = true;
        while(1){
          if(id[x] > id[y]) std::swap(x, y), d = not d;
          int l = std::max(id[head[y]], id[x]), r = id[y] + 1;
          if(l != r) ret.emplace_back(l, r, d);
          if(head[x] == head[y]) break;
          y = par[head[y]];
        }
      }

      x = y;
      y = w;

      {
        std::vector<std::tuple<int, int, bool>> temp;
        bool d = false;
        while(1){
          if(id[x] > id[y]) std::swap(x, y), d = not d;
          int l = std::max({id[head[y]], id[x], id[w] + 1}), r = id[y] + 1;
          if(l != r) temp.emplace_back(l, r, d);
          if(head[x] == head[y]) break;
          y = par[head[y]];
        }

        std::reverse(temp.begin(), temp.end());
        ret.insert(ret.end(), temp.begin(), temp.end());
      }

      return ret;
    }

    std::vector<std::pair<int, int>> path_query_edge(int x, int y) const {
      std::vector<std::pair<int, int>> ret;
      while(1){
        if(id[x] > id[y]) std::swap(x, y);
        if(head[x] == head[y]){
          if(x != y) ret.emplace_back(id[x] + 1, id[y] + 1);
          break;
        }
        ret.emplace_back(id[head[y]], id[y] + 1);
        y = par[head[y]];
      }
      return ret;
    }

    std::pair<int, int> subtree_query_edge(int x) const {
      return {id[x] + 1, end[x]};
    }

    std::pair<int, int> subtree_query_vertex(int x) const {
      return {id[x], end[x]};
    }

    int get_edge_id(int u, int v) const { // 辺に対応するid
      if(par[u] == v) return id[u];
      if(par[v] == u) return id[v];
      return -1;
    }

    int parent(int x) const {return par[x];};

    int lca(int u, int v) const {
      while(1){
        if(id[u] > id[v]) std::swap(u, v);
        if(head[u] == head[v]) return u;
        v = par[head[v]];
      }
    }

    int get_id(int x) const {
      return id[x];
    }
  };
}



namespace haar_lib {
  template <typename T>
  class lazy_segment_tree_with_coefficients {
    const int depth, size, hsize;
    std::vector<T> data, lazy, coeff;

    void propagate(int i){
      if(lazy[i] == 0) return;
      if(i < hsize){
        lazy[i << 1 | 0] = lazy[i] + lazy[i << 1 | 0];
        lazy[i << 1 | 1] = lazy[i] + lazy[i << 1 | 1];
      }
      data[i] = data[i] + lazy[i] * coeff[i];
      lazy[i] = 0;
    }

    T update(int i, int l, int r, int s, int t, const T &x){
      propagate(i);
      if(r <= s || t <= l) return data[i];
      if(s <= l && r <= t){
        lazy[i] += x;
        propagate(i);
        return data[i];
      }
      return data[i] =
        update(i << 1 | 0, l, (l + r) / 2, s, t, x) +
        update(i << 1 | 1, (l + r) / 2, r, s, t, x);
    }

    T get(int i, int l, int r, int x, int y){
      propagate(i);
      if(r <= x || y <= l) return 0;
      if(x <= l && r <= y) return data[i];
      return get(i << 1 | 0, l, (l + r) / 2, x, y) + get(i << 1 | 1, (l + r) / 2, r, x, y);
    }

  public:
    lazy_segment_tree_with_coefficients(){}
    lazy_segment_tree_with_coefficients(int n, std::vector<T> coeff_):
      depth(n > 1 ? 32 - __builtin_clz(n - 1) + 1 : 1),
      size(1 << depth),
      hsize(size / 2),
      data(size, 0),
      lazy(size, 0),
      coeff(size, 0)
    {
      for(int i = hsize; i < size; ++i) coeff[i] = coeff_[i - hsize];
      for(int i = hsize; --i >= 1;) coeff[i] = coeff[i << 1 | 0] + coeff[i << 1 | 1];
    }

    void update(int l, int r, const T &x){update(1, 0, hsize, l, r, x);}
    void update_at(int i, const T &x){update(i, i + 1, x);}
    T get(int l, int r){return get(1, 0, hsize, l, r);}
    T operator[](int i){return get(i, i + 1);}

    void init(const T &val){
      init_with_vector(std::vector<T>(hsize, val));
    }

    void init_with_vector(const std::vector<T> &val){
      data.assign(size, 0);
      lazy.assign(size, 0);
      for(int i = 0; i < (int)val.size(); ++i) data[hsize + i] = val[i];
      for(int i = hsize; --i >= 0;) data[i] = data[i << 1 | 0] + data[i << 1 | 1];
    }
  };
}

/**
 * @docs sort_simultaneously.md
 */
namespace haar_lib {
  template <typename Compare, typename ... Args>
  void sort_simultaneously(const Compare &compare, std::vector<Args> &... args){
    const int N = std::max({args.size() ...});
    std::vector<int> ord(N);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(), compare);

    (void)std::initializer_list<int>{
      (void(
        [&](){
          auto temp = args;
          for(int i = 0; i < N; ++i) temp[i] = args[ord[i]];
          std::swap(temp, args);
        }()
      ), 0) ...};
  }
}






namespace haar_lib {}

namespace solver {
  using namespace haar_lib;

  constexpr int m1000000007 = 1000000007;
  constexpr int m998244353 = 998244353;

  void init(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(12);
    std::cerr << std::fixed << std::setprecision(12);
    std::cin.exceptions(std::ios_base::failbit);
  }

  using mint = modint<m1000000007>;

  void solve(){
    int N; std::cin >> N;
    std::vector<mint> S(N); std::cin >> S;
    std::vector<mint> C(N); std::cin >> C;

    tree<int> tr(N);
    tr.read<1, false, false>(N - 1);

    auto hld = hl_decomposition(tr, 0);

    sort_simultaneously([&](int i, int j){return hld.get_id(i) < hld.get_id(j);}, S, C);

    auto seg = lazy_segment_tree_with_coefficients<mint>(N, C);
    seg.init_with_vector(S);

    int Q; std::cin >> Q;

    while(Q--){
      int type; std::cin >> type;

      if(type == 0){
        int X, Y, Z; std::cin >> X >> Y >> Z;
        --X, --Y;
        for(auto [l, r, d] : hld.path_query_vertex(X, Y)){
          seg.update(l, r, Z);
        }
      }else{
        int X, Y; std::cin >> X >> Y;
        --X, --Y;
        mint ans = 0;
        for(auto [l, r, d] : hld.path_query_vertex(X, Y)){
          ans += seg.get(l, r);
        }
        std::cout << ans << "\n";
      }
    }
  }
}

int main(){
  solver::init();
  while(true){
    try{
      solver::solve();
    }catch(const std::istream::failure &e){
      break;
    }
  }
  return 0;
}
yukicoder

結果

テストケース

ソースコード
