結果

問題 No.235 めぐるはめぐる (5)
ユーザー lumc_lumc_
提出日時 2018-08-18 17:49:17
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2,893 ms / 10,000 ms
コード長 10,668 bytes
コンパイル時間 1,946 ms
コンパイル使用メモリ 181,300 KB
実行使用メモリ 39,900 KB
最終ジャッジ日時 2024-11-06 09:40:56
合計ジャッジ時間 13,424 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,893 ms
39,216 KB
testcase_01 AC 1,562 ms
39,900 KB
testcase_02 AC 2,556 ms
39,412 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// #undef DEBUG
// #define DEBUG
/// {{{ DEBUG --- ///
#ifdef DEBUG
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { o << "{"; for(size_t i = 0; i < v.size(); i++) o << v[i] << (i + 1 != v.size() ? ", " : ""); o << "}"; return o; }
#ifdef USE_COUT
#define dump(...) [&](){auto __debug_tap=make_tuple(__VA_ARGS__);cout<<"["<<__LINE__<< "] "<<#__VA_ARGS__<<" = "<<__debug_tap<<"\n";}()
#else
#define dump(...) [&](){auto __debug_tap=make_tuple(__VA_ARGS__);cerr<<"["<<__LINE__<< "] "<<#__VA_ARGS__<<" = "<<__debug_tap<<"\n";}()
#endif
template<class T> inline void dump2D(T &d, size_t sizey, size_t sizex) { ostream&o=
#ifdef USE_COUT
  cout;
#else
  cerr;
#endif
  for(size_t i = 0; i < sizey; i++) { for(size_t j = 0; j < sizex; j++) o << d[i][j] << " "; o << endl; }
}
#else
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { for(size_t i = 0; i < v.size(); i++) o << v[i] << (i + 1 != v.size() ? " " : ""); return o; }
#define dump(...) (42)
#define dump2D(...) (42)
#endif
template<int n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple<T...> const &){}
template<int n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple<T...> const & t){ os << (n==0?"":", ") << get<n>(t); _ot<n+1>(os, t); }
template<class...T> ostream & operator<<(ostream &o, tuple<T...> const &t){ o << "("; _ot<0>(o, t); o << ")"; return o; }
template<class T, class U> ostream & operator<<(ostream &o, pair<T, U> const &p) { o << "(" << p.first << ", " << p.second << ")"; return o; }
/// }}}--- ///

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll extgcd(ll a, ll b, ll &x, ll &y) { ll d; return b == 0 ? (x = 1, y = 0, a) : (d = extgcd(b, a % b, y, x), y -= a / b * x, d); }
ll modinv(ll a, ll mod = 1e9 + 7) { ll x = 0, y = 0; extgcd(a, mod, x, y); return (x + mod) % mod; }
ll modpow(ll a, ll b, ll mod = 1e9 + 7) { ll r = 1; a %= mod; while(b) { if(b & 1) r = r * a % mod; a = a * a % mod; b >>= 1; } return r; }

const ll mod = 1e9 + 7;
const int N = 2e5;
int n;

// require math library
/// ModInt Library {{{ ///
template<long long mod = (long long)1e9 + 7>
struct ModInt{
  long long val;
  ModInt() : val(0) {}
  ModInt(long long val) : val((val % mod + mod) % mod) {}
  operator int() const { return val; }
  operator long long() const { return val; }
  ModInt operator+(ModInt const &rhs) const {
    return ModInt(val + rhs.val);
  }
  ModInt operator-(ModInt const &rhs) const {
    return ModInt(val - rhs.val);
  }
  ModInt operator*(ModInt const &rhs) const {
    return ModInt(val * rhs.val);
  }
  ModInt operator/(ModInt const &rhs) const {
    return ModInt(val * rhs.inv().val);
  }
  ModInt &operator+=(ModInt const &rhs) {
    val = ((val + rhs.val) % mod + mod) % mod;
    return *this;
  }
  ModInt &operator-=(ModInt const &rhs) {
    val = ((val - rhs.val) % mod + mod) % mod;
    return *this;
  }
  ModInt &operator*=(ModInt const &rhs) {
    val = (val * rhs.val % mod + mod) % mod;
    return *this;
  }
  ModInt &operator/=(ModInt const &rhs) {
    val = (val * rhs.inv().val % mod + mod) % mod;
    return *this;
  }
  ModInt operator++(int) {
    ModInt tmp = *this;
    val = val + 1;
    if(val >= mod) val = 0;
    return tmp;
  }
  ModInt operator--(int) {
    ModInt tmp = *this;
    val = val == 0 ? mod - 1 : val - 1;
    return tmp;
  }
  ModInt &operator++() {
    val = val + 1;
    if(val >= mod) val = 0;
    return *this;
  }
  ModInt &operator--() {
    val = val == 0 ? mod - 1 : val - 1;
    return *this;
  }
  template<typename T> ModInt operator+(T const &rhs) const {
    return ModInt(val + rhs % mod);
  }
  template<typename T> ModInt operator-(T const &rhs) const {
    return ModInt(val - rhs % mod);
  }
  template<typename T> ModInt operator*(T const &rhs) const {
    return ModInt(val * (rhs % mod));
  }
  template<typename T> ModInt operator/(T const &rhs) const {
    return ModInt(val * modinv(rhs, mod));
  }
  template<typename T> ModInt &operator+=(T const &rhs) {
    val = ((val + rhs % mod) % mod + mod) % mod;
    return *this;
  }
  template<typename T> ModInt &operator-=(T const &rhs) {
    val = ((val - rhs % mod) % mod + mod) % mod;
    return *this;
  }
  template<typename T> ModInt &operator*=(T const &rhs) {
    val = (val * (rhs % mod) % mod + mod) % mod;
    return *this;
  }
  template<typename T> ModInt &operator/=(T const &rhs) {
    val = (val * modinv(rhs, mod) % mod + mod) % mod;
    return *this;
  }
  ModInt inv() const {
    return ModInt(modinv(val, mod));
  }
  friend ostream &operator<<(ostream &os, ModInt const &mv) { os << mv.val; return os; }
  friend constexpr ModInt operator+(long long a, ModInt const &mv) { return ModInt(a % mod + mv.val); }
  friend constexpr ModInt operator-(long long a, ModInt const &mv) { return ModInt(a % mod - mv.val); }
  friend constexpr ModInt operator*(long long a, ModInt const &mv) { return ModInt(a % mod * mv.val); }
  friend constexpr ModInt operator/(long long a, ModInt const &mv) { return ModInt(a % mod * mv.inv().val); }
};
/// }}}-- ///

using Int = ModInt<mod>;

// a[i]に区間add
// 区間sum a[i] * b[i]
// を高速に求めたい
//
// {{{

template<class T>
struct StarrySkyTree {
  int n;
  vector<T> data;
  vector<T> all;
  vector<T> bsum;
  int topbit(int x) {
    x = x & 0xFFFF0000 ? x & 0xFFFF0000 : x;
    x = x & 0xFF00FF00 ? x & 0xFF00FF00 : x;
    x = x & 0xF0F0F0F0 ? x & 0xF0F0F0F0 : x;
    x = x & 0xCCCCCCCC ? x & 0xCCCCCCCC : x;
    x = x & 0xAAAAAAAA ? x & 0xAAAAAAAA : x;
    return x;
  }
  StarrySkyTree(int t) {
    n = topbit(t);
    if(n < t) n <<= 1;
    data.resize((n << 1) - 1);
    all.resize((n << 1) - 1);
    bsum.resize(n);
  }
  template<class InputIter, class = typename std::iterator_traits<InputIter>::value_type>
  StarrySkyTree(InputIter first, InputIter last)
  : StarrySkyTree(distance(first, last)) {
    copy(first, last, begin(bsum));
    for(int i = 1; i < n; i++) bsum[i] = bsum[i - 1] + bsum[i];
  }
  void act(int a, int b, T x, int l = 0, int r = -1, int k = 0) {
    if(r < 0) r = n;
    if(b <= l || r <= a) return;
    if(a <= l && r <= b) {
      all[k] = all[k] + x;
      return;
    }
    act(a, b, x, l, (l + r) >> 1, k * 2 + 1);
    act(a, b, x, (l + r) >> 1, r, k * 2 + 2);
    data[k] = data[k * 2 + 1] + data[k * 2 + 2] +
      all[k * 2 + 1] * getRangeB(l, (l + r) >> 1) +
      all[k * 2 + 2] * getRangeB((l + r) >> 1, r);
  }
  T getRangeB(int l, int r) {
    T res = bsum[r - 1];
    if(l - 1 >= 0) res -= bsum[l - 1];
    return res;
  }
  const T identity = 0;
  T query(int a, int b, int l = 0, int r = -1, int k = 0, ll sum = 0) {
    if(r < 0) r = n;
    if(b <= l || r <= a) return identity;
    sum = sum + all[k];
    if(a <= l && r <= b) return sum * getRangeB(l, r) + data[k];
    return
      query(a, b, l, (l + r) >> 1, k * 2 + 1, sum) +
      query(a, b, (l + r) >> 1, r, k * 2 + 2, sum);
  }
};

// }}}

/// --- Graph Template {{{ ///

template<class T>
struct Edge {
  int from, to; T cost;
  Edge(int to, T cost) : from(-1), to(to), cost(cost) {}
  Edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
};
template<class T>
using WeightedGraph = vector< vector< Edge<T> > >;
using UnWeightedGraph = vector< vector<int> >;
inline void read(int &n, int &m, UnWeightedGraph &g) {
  cin >> n >> m;
  g.resize(n);
  for(int i = 0; i < m; i++) {
    int a, b; cin >> a >> b; a--; b--;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
}

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

ll s[N], c[N];

vector<int> g[N];

// query(hi, lo, func, inclusive?)
// hld[i] : index on sequence
// WARN : build after adding edges!
/// --- HL-Decomposition Library {{{ ///

struct HLD {
  int n;
  vector<int> head;
  vector<int> sz;
  vector<int> dep;
  vector<int> par;
  vector<int> vid;
  int id = 0;
  UnWeightedGraph g; // tree
  HLD(int n): n(n), head(n), sz(n), dep(n), par(n), vid(n), g(n) {}
  HLD(UnWeightedGraph g, int root = 0): HLD(g.size()) { this->g = g; build(root); }
  int operator[](int i) { return vid[i]; }
  void addEdge(int a, int b) {
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  void build(int root = 0) {
    head[root] = root;
    dfs0(root, -1, 0); dfs1(root, -1);
  }
  int lca(int a, int b) {
    while(1) {
      if(vid[a] > vid[b]) swap(a, b);
      dump(a, b);
      dump(vid[a], vid[b]);
      dump(head[a], head[b]);
      if(head[a] == head[b]) return a;
      b = par[head[b]];
    }
  }
  void query(int hi, int lo, function<void(int, int)> f, bool inclusive = true) {
    while(lo != -1 && dep[lo] >= dep[hi]) {
      int nex = max(vid[head[lo]], vid[hi]);
      f(nex + (nex == vid[hi] && !inclusive), vid[lo] + 1);
      lo = par[head[lo]];
    }
  }
private:
  void dfs0(int i, int p, int d) {
    par[i] = p;
    sz[i] = 1;
    dep[i] = d;
    for(int &j : g[i]) if(j != p) {
      dfs0(j, i, d + 1);
      sz[i] += sz[j];
      if(sz[j] > sz[g[i][0]]) {
        swap(g[i][0], j);
      }
    }
  }
  void dfs1(int i, int p) {
    vid[i] = id++;
    for(int j : g[i]) if(j != p) {
      head[j] = j == g[i][0] ? head[i] : j;
      dfs1(j, i);
    }
  }
};

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

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  cin >> n;
  for(int i = 0; i < n; i++) cin >> s[i];
  for(int i = 0; i < n; i++) cin >> c[i];
  HLD hld(n);
  for(int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b; a--; b--;
    hld.addEdge(a, b);
  }
  hld.build();
  vector<Int> k(n);
  for(int i = 0; i < n; i++) k[hld[i]] = c[i];
  StarrySkyTree<Int> qina(begin(k), end(k));
  vector<Int> ecas(n);
  for(int i = 0; i < n; i++) {
    ecas[hld[i]] = s[i];
  }
  for(int i = 1; i < n; i++) {
    ecas[i] = ecas[i] + ecas[i - 1];
  }
  int q;
  cin >> q;
  while(q--) {
    int c;
    cin >> c;
    if(c == 0) { // update
      int s, t, k;
      cin >> s >> t >> k;
      s--; t--;
      int lca = hld.lca(s, t);
      // dump(s, t, lca);
      auto f = [&](int l, int r) {
        // dump("!", q, l, r);
        qina.act(l, r, k);
      };
      hld.query(lca, s, f);
      hld.query(lca, t, f, 0);
    } else { // ask
      int s, t;
      cin >> s >> t;
      s--; t--;
      int lca = hld.lca(s, t);
      // dump(lca, s, t);
      // dump(dep[lca], dep[s], dep[t]);
      Int res = 0;
      auto f = [&](int l, int r) {
        // dump("?", q, l, r);
        res += qina.query(l, r);
        res += ecas[r - 1];
        if(l - 1 >= 0) res -= ecas[l - 1];
      };
      hld.query(lca, s, f);
      hld.query(lca, t, f, 0);
      cout << res << endl;
    }
  }
  return 0;
}
0