結果

問題 No.235 めぐるはめぐる (5)
ユーザー okaduki
提出日時 2017-11-05 22:57:42
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 1,026 ms / 10,000 ms
コード長 6,551 bytes
コンパイル時間 2,262 ms
コンパイル使用メモリ 184,084 KB
実行使用メモリ 50,788 KB
最終ジャッジ日時 2024-11-24 02:57:54
合計ジャッジ時間 8,031 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;
#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1000000007;
struct Edge{
  int to, cost;
  Edge(int t, int c = 0): to(t), cost(c)
  {}
  bool operator>(const Edge& rhs) const{
    return cost > rhs.cost;
  }
  bool operator<(const Edge& rhs) const{
    return cost < rhs.cost;
  }
};
using Graph = vector<vector<Edge>>;
void add_edge(Graph& graph, int u, int v, int cost = 0){
  graph[u].push_back(Edge(v,cost));
  graph[v].push_back(Edge(u,cost));
}
class LazySegT{
private:
  int NN;
  struct Node{
    LL dat;
    LL lazy;
    LL S;
  };
  vector<Node> segT;
public:
  LazySegT(int n, VL& x0, VL& s0){
    NN = 1;
    while(NN < n) NN <<= 1;
    segT.resize(NN*2);
    for(int i=0;i<n;++i){
      segT[NN-1+i].dat = x0[i];
      segT[NN-1+i].S = s0[i];
      segT[NN-1+i].lazy = 0;
    }
    for(int i=NN-2;i>=0;--i){
      segT[i].dat = (segT[i*2+1].dat + segT[i*2+2].dat) % MOD;
      segT[i].S = (segT[i*2+1].S + segT[i*2+2].S) % MOD;
      segT[i].lazy = 0;
    }
  }
  void eval(int k, int l, int r){
    if(segT[k].lazy == 0) return;
    
    (segT[k].dat += segT[k].lazy * segT[k].S % MOD) %= MOD;
    if(k < NN-1){ // not leaf
      (segT[2*k+1].lazy += segT[k].lazy) %= MOD;
      (segT[2*k+2].lazy += segT[k].lazy) %= MOD;
    }
    segT[k].lazy = 0;
  }
  void update(int a, int b, LL c, int k, int l, int r){
    eval(k,l,r);
    if(r <= a || b <= l) return;
    if(a <= l && r <= b){
      (segT[k].lazy += c) %= MOD;
      eval(k,l,r);
    }
    else{
      update(a, b, c, k*2+1, l, (l+r)/2);
      update(a, b, c, k*2+2, (l+r)/2, r);
      segT[k].dat = (segT[k*2+1].dat + segT[k*2+2].dat) % MOD;
    }
  }
  // dat[idx] += c, a <= idx < b
  void update(int a, int b, LL c){
    update(a, b, c, 0, 0, NN);
  }
  LL query(int a, int b, int k, int l, int r){
    eval(k,l,r);
    if(r <= a || b <= l) return 0;
    if(a <= l && r <= b) return segT[k].dat;
    else{
      LL vl = query(a, b, k*2+1, l, (l+r)/2);
      LL vr = query(a, b, k*2+2, (l+r)/2, r);
      segT[k].dat = (segT[k*2+1].dat + segT[k*2+2].dat) % MOD;
      return (vl+vr) % MOD;
    }
  }
  LL query(int a, int b){
    return query(a, b, 0, 0, NN);
  }
};
/**
 * HL分解
 * 
 * あらゆる部分木の深さがO(log n)になるように分解する。
 * 部分木のうちサイズが最も大きいものへの辺をHeavy、それ以外をLightに分ける。
 * Heavyな辺はたかだか一つであるのでSegment Treeなどで管理可能。
 */
struct HL{
  int N;
  VI depth;
  VI par;
  VI sz;
  //! 辺のコストは頂点に移す
  VI xs;
  //! 頂点が所属するHeavyのid
  VI heavy_id;
  //! 何番目の頂点か
  VI heavy_nth;
  //! heavys[id] := {idのHeavyの頂点の列}
  VVI heavys;
  //! Heavyからなる部分木としたときの親のheavy_id
  VI heavy_par;
  //! heavyの数
  int H;
  HL(const Graph& G, int root = 0, const VI& xs_ = {}){
    N = SZ(G);
    depth.assign(N, 0);
    par.assign(N, -1);
    sz.assign(N, 1);
    if(!xs_.empty())
      xs = xs_;
    else
      xs.assign(N, 0);
    heavy_id.assign(N, -1);
    heavy_nth.assign(N, 0);
    heavys.assign(N, {});
    heavy_par.assign(N, -1);
    function<void(int,int)> init = [&](int u, int p){
      par[u] = p;
      for(auto& e: G[u]){
        if(e.to == p) continue;
        depth[e.to] = depth[u] + 1;
        init(e.to, u);
        sz[u] += sz[e.to];
        if(xs_.empty())
          xs[e.to] = e.cost;
      }
    };
    depth[root] = 0;
    init(root, -1);
    H = 1;
    function<void(int,int)> calcHL = [&](int u, int p){
      heavy_nth[u] = SZ(heavys[heavy_id[u]]);
      heavys[heavy_id[u]].PB(u);
      int max_u = -1;
      for(auto& e: G[u]){
        if(e.to == p) continue;
        if(max_u < 0 || sz[max_u] < sz[e.to])
          max_u = e.to;
      }
      if(max_u < 0) return;
      heavy_id[max_u] = heavy_id[u];
      calcHL(max_u, u);
      
      for(auto& e: G[u]){
        if(e.to == p || e.to == max_u) continue;
        heavy_id[e.to] = H++;
        calcHL(e.to, u);
        heavy_par[heavy_id[e.to]] = heavy_id[u];
      }
    };
    heavy_id[root] = 0;
    calcHL(root, -1);
  }
  int LCA(int u, int v){
    while(true){
      if(heavy_id[u] == heavy_id[v])
        return (depth[u] <= depth[v]? u: v);
      int ru = heavys[heavy_id[u]][0];
      int rv = heavys[heavy_id[v]][0];
      if(depth[ru] < depth[rv])
        v = par[rv];
      else
        u = par[ru];
    }
  }
  vector<LazySegT> segs;
  void initSegs(VI& cs){
    REP(i,H){
      int n = SZ(heavys[i]);
      VL x0(n), s0(n);
      REP(k,n){
        int id = heavys[i][k];
        x0[k] = xs[id];
        s0[k] = cs[id];
      }
      segs.EB(n, x0, s0);
    }
  }
  // Require: p is ancestor of u
  void add(int p, int u, LL x){
    while(heavy_id[p] != heavy_id[u]){
      int hid = heavy_id[u];
      segs[hid].update(0, heavy_nth[u]+1, x);
      u = par[heavys[hid][0]];
    }
    int hid = heavy_id[u];
    segs[hid].update(heavy_nth[p], heavy_nth[u]+1, x);
  }
  // Require: p is ancestor of u
  LL query(int p, int u){
    LL res = 0;
    while(heavy_id[p] != heavy_id[u]){
      int hid = heavy_id[u];
      (res += segs[hid].query(0, heavy_nth[u]+1)) %= MOD;
      u = par[heavys[hid][0]];
    }
    int hid = heavy_id[u];
    (res += segs[hid].query(heavy_nth[p], heavy_nth[u]+1)) %= MOD;
    return res;
  }
};
int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int N;
  cin >> N;
  VI xs(N), cs(N);
  REP(i,N) cin >> xs[i];
  REP(i,N) cin >> cs[i];
  Graph G(N);
  REP(i,N-1){
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    add_edge(G, a, b);
  }
  auto hl = HL(G, 0, xs);
  hl.initSegs(cs);
  
  int Q;
  cin >> Q;
  while(Q--){
    int T;
    int x, y, z;
    cin >> T >> x >> y;
    --x;
    --y;
    if(!T){
      cin >> z;
      int lca = hl.LCA(x, y);
      hl.add(lca, x, z);
      hl.add(lca, y, z);
      hl.add(lca, lca, MOD-z);
    }
    else{
      int lca = hl.LCA(x, y);
      cout << (hl.query(lca, x) + hl.query(lca, y) + MOD - hl.query(lca, lca))%MOD << endl;
    }
  }
  return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0