結果

問題 No.235 めぐるはめぐる (5)
ユーザー Kutimoti_TKutimoti_T
提出日時 2018-08-22 14:31:54
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,770 ms / 10,000 ms
コード長 8,326 bytes
コンパイル時間 3,473 ms
コンパイル使用メモリ 184,012 KB
実行使用メモリ 49,036 KB
最終ジャッジ日時 2023-08-25 15:41:56
合計ジャッジ時間 11,376 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,770 ms
48,072 KB
testcase_01 AC 1,219 ms
49,036 KB
testcase_02 AC 1,631 ms
48,204 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

long long inv_mod(long long a, long long m) {
  long long b, x, u, q, abs_m, tmp;

  abs_m = (m < 0) ? -m : m;
  b = m;
  x = 1;
  u = 0;
  while (b > 0) {
    q = a / b;
    tmp = u;
    u = x - q * u;
    x = tmp;
    tmp = b;
    b = a - q * b;
    a = tmp;
  }

  return (x < 0) ? abs_m + x : x;
}
template <long long MOD>
struct ModInt{
  long long value;

  ModInt(long long n = 0) : value(n % MOD){}


  operator long long() const noexcept {return value % MOD;}

  ModInt<MOD> operator++(int){
    ModInt<MOD> before = *this;
    value = (value + 1) % MOD;
    return before;
  }

  ModInt<MOD> operator--(int){
    ModInt<MOD> before = *this;
    value = (value - 1 + MOD) % MOD;
    return before;
  }

  ModInt<MOD>& operator++(){
    value = (value + 1) % MOD;
    return *this;
  }

  ModInt<MOD>& operator--(){
    value = (value - 1 + MOD) % MOD;
    return *this;
  }

  bool operator!() const noexcept{
    return !static_cast<bool>(value);
  }

  ModInt<MOD> operator+() const{
    return value;
  }
  
  ModInt<MOD> operator-() const{
    return (-value + MOD) % MOD;
  }

  ModInt<MOD>& operator*=(const ModInt<MOD>& m){
    return *this = ModInt<MOD>((this->value * m.value) % MOD);
  }
  ModInt<MOD>& operator+=(const ModInt<MOD>& m){
    return *this = ModInt<MOD>((this->value + m.value) % MOD);
  }
  ModInt<MOD>& operator-=(const ModInt<MOD>& m){
    return *this = ModInt<MOD>((this->value - m.value + MOD) % MOD);
  }
  ModInt<MOD>& operator/=(const ModInt<MOD>& m){
    return *this = ModInt<MOD>((this->value * inv_mod(m.value,MOD)) % MOD);
  }
 };

template<long long MOD>
ModInt<MOD> operator*(const ModInt<MOD>& m1,const ModInt<MOD>& m2){return ModInt<MOD>(m1) *= m2;}
template<long long MOD>
ModInt<MOD> operator+(const ModInt<MOD>& m1,const ModInt<MOD>& m2){return ModInt<MOD>(m1) += m2;}
template<long long MOD>
ModInt<MOD> operator-(const ModInt<MOD>& m1,const ModInt<MOD>& m2){return ModInt<MOD>(m1) -= m2;}
template<long long MOD>
ModInt<MOD> operator/(const ModInt<MOD>& m1,const ModInt<MOD>& m2){return ModInt<MOD>(m1) /= m2;}
template<long long MOD>
ModInt<MOD> operator*(const long long& m1,const ModInt<MOD>& m2){return ModInt<MOD>(m1) *= m2;}
template<long long MOD>
ModInt<MOD> operator+(const long long& m1,const ModInt<MOD>& m2){return ModInt<MOD>(m1) += m2;}
template<long long MOD>
ModInt<MOD> operator-(const long long& m1,const ModInt<MOD>& m2){return ModInt<MOD>(m1) -= m2;}
template<long long MOD>
ModInt<MOD> operator/(const long long& m1,const ModInt<MOD>& m2){return ModInt<MOD>(m1) /= m2;}

/* include file*/
#include <functional>
#include <vector>
using namespace std;

template <class Monoid>
struct LazySegment {
  using Func = function<Monoid(Monoid, Monoid)>;
  vector<Monoid> node;
  vector<Monoid> lazy;
  vector<Monoid> ls;
  vector<bool> lazyFlag;
  int n;
  Monoid ide;
  Monoid lazy_init;

  Monoid func(Monoid a,Monoid b){
    return a + b;
  }

  Monoid lazy_make(int l,int r,Monoid x,Monoid lazy){
    return lazy + x;
  }

  Monoid lazy_effect(Monoid node,Monoid lazy,int k){
    return node + lazy * ls[k];
  }

  Monoid lazy_throw(Monoid from,Monoid to){
    return to + from;
  }

  LazySegment(const vector<Monoid> init, Monoid ide_, Monoid lazy_i)
      : ide(ide_), lazy_init(lazy_i) {
    n = 1;
    int sz = init.size();
    while (n < sz) n *= 2;

    node.resize(n * 2 - 1, ide);
    lazy.resize(n * 2 - 1, lazy_init);
    lazyFlag.resize(n * 2 - 1, false);

    for (int i = 0; i < sz; i++) node[i + n - 1] = init[i];
    for (int i = n - 2; i >= 0; i--)
      node[i] = func(node[i * 2 + 1], node[i * 2 + 2]);
  }

  void eval(int k, int l, int r) {
    if (lazyFlag[k]) {
      node[k] = lazy_effect(node[k], lazy[k],k);

      if (r - l > 1) {
        lazy[2 * k + 1] = lazy_throw(lazy[k], lazy[2 * k + 1]);
        lazy[2 * k + 2] = lazy_throw(lazy[k], lazy[2 * k + 2]);
        lazyFlag[2 * k + 1] = true;
        lazyFlag[2 * k + 2] = true;
      }

      lazyFlag[k] = false;
      lazy[k] = lazy_init;
    }
  }

  void update_inter(int a, int b, Monoid x, int k = 0, int l = 0, int r = -1) {
    if (r < 0) r = n;

    eval(k, l, r);

    if (r <= a || b <= l) return;

    if (a <= l && r <= b) {
      lazy[k] = lazy_make(l, r, x, lazy[k]);
      lazyFlag[k] = true;
      eval(k, l, r);
    } else {
      update_inter(a, b, x, k * 2 + 1, l, (l + r) / 2);
      update_inter(a, b, x, k * 2 + 2, (l + r) / 2, r);
      node[k] = func(node[k * 2 + 1], node[k * 2 + 2]);
    }
  }

  Monoid get_inter(int a, int b, int k = 0, int l = 0, int r = -1) {
    if (r < 0) r = n;

    eval(k, l, r);

    if (r <= a || b <= l) return ide;

    if (a <= l && r <= b) return node[k];

    Monoid lm = get_inter(a, b, k * 2 + 1, l, (l + r) / 2);
    Monoid rm = get_inter(a, b, k * 2 + 2, (l + r) / 2, r);
    return func(lm, rm);
  }
};

const long long mm = 1e9 + 7;
using Int = ModInt<mm>;

#include <vector>
#include <set>
#include <stack>
#include <queue>
using namespace std;
using i64 = long long;

struct HLDecomposition{
  int n,pos;
  vector<vector<int> > G;
  vector<int> vid,head,hvy,par,dep,inv,sub;

  LazySegment<Int> seg;

  HLDecomposition(int sz):
    n(sz),pos(0),G(n),
    vid(n,-1),head(n),hvy(n,-1),
    par(n),dep(n),inv(n),sub(n,1),seg(vector<Int>(0),0,0){}
  
  void add_edge(int u,int v){
    G[u].push_back(v);
    G[v].push_back(u);
  }

  void dfs(int rt){
    typedef pair<int,int> T;
    stack<T> st;
    par[rt] = -1;
    dep[rt] = 0;
    st.push(make_pair(rt,0));
    while(!st.empty()){
      int v= st.top().first;
      int &i = st.top().second;
      if(i < (int)G[v].size()){
        int u = G[v][i++];
        if(u == par[v]) continue;
        par[u] = v;
        dep[u] = dep[v] + 1;
        st.push(make_pair(u,0));
      }
      else{
        st.pop();
        int res = 0;
        for(int i = 0;i < (int)G[v].size();i++){
          int u = G[v][i];
          if(u == par[v]) continue;
          sub[v] += sub[u];
          if(res < sub[u]) res = sub[u],hvy[v] = u;
        }
      }
    }
  }

  void bfs(int r){
    int &k = pos;
    queue<int> q;
    q.push(r);
    while(!q.empty()){
      int h = q.front();
      q.pop();
      for(int i = h;i != -1;i = hvy[i]){
        vid[i] = k++;
        inv[vid[i]] = i;
        head[i] = h;
        for(int j = 0;j < (int)G[i].size();j++){
          int u = G[i][j];
          if(u != par[i] && u != hvy[i]) q.push(u);
        }
      }
    }
  }

  void build(int r){
    dfs(r);
    bfs(r);
  }

  void f(int l,int r,i64 z){
    seg.update_inter(l,r + 1,z);
  }

  i64 f2(int l,int r){
    return seg.get_inter(l,r + 1);
  }

  void for_vertex(int u,int v,i64 z){
    while(1){
      if(vid[u] > vid[v]) swap(u,v);
      f(max(vid[head[v]],vid[u]),vid[v],z);
      if(head[u] != head[v]) v= par[head[v]];
      else break;
    }
  }
  i64 for_vertex2(int u,int v){
    i64 sum = 0;
    while(1){
      if(vid[u] > vid[v]) swap(u,v);
      sum += f2(max(vid[head[v]],vid[u]),vid[v]);
      if(head[u] != head[v]) v= par[head[v]];
      else break;
    }
    return sum;
  }

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

  int distance(int u,int v){
    return dep[u] + dep[v] - 2 * dep[lca(u,v)];
  }
};

int N;

vector<i64> S,C;

int main(){
  cin >> N;
  S.resize(N);
  C.resize(N);
  rep(i,0,N - 1) cin >> S[i];
  rep(i,0,N - 1) cin >> C[i];


  HLDecomposition hld(N);

  rep(i,0,N -2){
    int a,b;
    cin >> a >> b;
    a--;
    b--;
    hld.add_edge(a,b);
  }
  hld.build(0);
  int Q;
  cin >> Q;
  vector<Int> ans;
  vector<Int> s(N);
  vector<Int> c(N);
  rep(i,0,N - 1){
    s[hld.vid[i]] = S[i];
    c[hld.vid[i]] = C[i];
  }
  hld.seg = LazySegment<Int>(s,0,0);
  {
    LazySegment<Int> seg(c,0,0);
    hld.seg.ls = seg.node;
  }

  rep(i,0,Q - 1){
    int t;
    cin >> t;
    if(t == 0){
      i64 x,y,z;
      cin >> x >> y >> z;
      x--;
      y--;
      hld.for_vertex(x,y,z);
    }
    else{
      i64 x,y;
      cin >> x >> y;
      x--;
      y--;
      ans.push_back(hld.for_vertex2(x,y));
    }

  }
  for(int i = 0;i < ans.size();i++){
    cout << ans[i] << endl;
  }
  return 0;
}
0