結果

問題 No.235 めぐるはめぐる (5)
ユーザー ferinferin
提出日時 2018-08-11 00:50:47
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 6,958 bytes
コンパイル時間 2,015 ms
コンパイル使用メモリ 183,944 KB
実行使用メモリ 43,424 KB
最終ジャッジ日時 2024-09-23 06:03:01
合計ジャッジ時間 8,645 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll INF = (1LL<<60);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int C[200010], csum[200010];
struct HLDecomposition {
  int n, pos;
  VVI g;
  VI vid,   // HL分解後のグラフでのid
     head,  // 頂点が属するheavy-pathのheadのid
     sub,   // 部分木のサイズ
     hvy,   // heavy-path上での次の頂点のid
     par,   // 親のid
     depth, // 深さ
     inv,   // HL分解前のグラフのid（添え字が分解後のid）
     type;  // 森をHL分解するときの属する木の番号

  HLDecomposition(){}
  HLDecomposition(int sz):
    n(sz), pos(0), g(n),
    vid(n,-1), head(n), sub(n,1), hvy(n,-1),
    par(n), depth(n), inv(n), type(n) {}

  void add_edge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
  }

  void build(VI rs=VI(1,0)) {
    int c=0;
    for(int r: rs){
      dfs(r);
      bfs(r, c++);
    }
  }

  void dfs(int rt) {
    stack<PII> st;
    par[rt] = -1;
    depth[rt] = 0;
    st.emplace(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;
      	depth[u] = depth[v]+1;
      	st.emplace(u,0);
      } else {
      	st.pop();
      	int ma = 0;
      	for(int u: g[v]){
      	  if(u == par[v]) continue;
      	  sub[v] += sub[u];
      	  if(ma < sub[u]) ma = sub[u], hvy[v] = u;
      	}
      }
    }
  }

  void bfs(int r, int c) {
    int &k = pos;
    queue<int> que;
    que.push(r);
    while(que.size()) {
      int h = que.front(); que.pop();
      for(int i=h; i!=-1; i=hvy[i]) {
      	type[i] = c;
      	vid[i] = k++;
      	inv[vid[i]] = i;
      	head[i] = h;
	      for(int j: g[i]) {
          if(j!=par[i] && j!=hvy[i]) que.push(j);
        }
      }
    }
  }

  // for_each(vertex)
  // [u,v] <- attention!!
  void for_each(int u, int v, const function<void(int, int)>& f) {
    while(1){
      if(vid[u]>vid[v]) swap(u,v);
      // [max(vid[head[v]],vid[u]), vid[v]] の区間についての操作を行う
      f(max(vid[head[v]], vid[u]), vid[v]);
      if(head[u]!=head[v]) v = par[head[v]];
      else break;
    }
  }

  // for_each(edge)
  // [u,v] <- attention!!
  void for_each_edge(int u, int v, const function<void(int, int)>& f) {
    while(1) {
      if(vid[u]>vid[v]) swap(u,v);
      if(head[u]!=head[v]) {
	      f(vid[head[v]], vid[v]);
        v = par[head[v]];
      } else {
	      if(u!=v) f(vid[u]+1, vid[v]);
	      break;
      }
    }
  }

  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 depth[u] + depth[v] - 2*depth[lca(u,v)];
  }
};

// 遅延セグメントツリー
template <typename T, typename E>
struct segtree {
  using F = function<T(T,T)>;
  using G = function<T(T,E)>;
  using H = function<E(E,E)>;
  using P = function<E(E,int)>;
  F f; G g; H h; P p; T d1; E d0;
  int n;
  vector<int> dat, lazy;

  segtree(){}
  segtree(int n_, F f_, G g_, H h_, T d1_, E d0_, P p_=[](E a, int b){return a;}):
    f(f_), g(g_), h(h_), p(p_), d1(d1_), d0(d0_) {
    n = 1; while(n < n_) n *= 2;
    dat.assign(n*2, d1);
    lazy.assign(n*2, d0);
  }
  void build(vector<T> v) {
    REP(i, v.size()) dat[i+n-1] = v[i];
    for(int i=n-2; i>=0; --i) dat[i] = f(dat[i*2+1], dat[i*2+2]);
  }

  // 区間の幅がlenの節点kについて遅延評価
  inline void eval(int l, int r, int k) {
    if(lazy[k] == d0) return;
    if(k*2+1 < n*2-1) {
      lazy[2*k+1] = h(lazy[k*2+1], lazy[k]);
      lazy[2*k+2] = h(lazy[k*2+2], lazy[k]);
    }
    dat[k] = g(dat[k],p(lazy[k],csum[r-1]-(l==0?0:csum[l-1])));
    lazy[k] = d0;
  }
  // [a, b)
  T update(int a, int b, E x, int k, int l, int r) {
    eval(l, r, k);
    if(b <= l || r <= a) return dat[k];
    if(a <= l && r <= b) {
      lazy[k] = h(lazy[k], x);
      return g(dat[k], p(lazy[k],csum[r-1]-(l==0?0:csum[l-1])));
    }
    return dat[k] = f(update(a, b, x, 2*k+1, l, (l+r)/2),
                      update(a, b, x, 2*k+2, (l+r)/2, r));
  }
  T update(int a, int b, E x) { return update(a, b, x, 0, 0, n); }
  // [a, b)
  T query(int a, int b, int k, int l, int r) {
    eval(l, r, k);
    if(a <= l && r <= b) return dat[k];
    bool left = !((l+r)/2 <= a || b <= l), right = !(r <= 1 || b <= (l+r)/2);
    if(left&&right) return f(query(a, b, 2*k+1, l, (l+r)/2), query(a, b, 2*k+2, (l+r)/2, r));
    if(left) return query(a, b, 2*k+1, l, (l+r)/2);
    return query(a, b, 2*k+2, (l+r)/2, r);
  }
  T query(int a, int b) { return query(a, b, 0, 0, n); }
  // デバッグ出力
  void debug() {
    cout << "---------------------" << endl;
    int cnt = 0;
    for(int i=1; i<=n; i*=2) {
      REP(j, i) {cout << "(" << dat[cnt] << "," << lazy[cnt] << ") "; cnt++;}
      cout << endl;
    }
    cout << "---------------------" << endl;
  }
};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n;
  cin >> n;
  HLDecomposition hld(n);
  VI s(n);
  REP(i, n) cin >> s[i];
  REP(i, n) cin >> C[i];
  REP(i, n-1) {
    int a, b; cin >> a >> b; a--, b--;
    hld.add_edge(a, b);
  }
  hld.build();

  auto f = [](int l, int r){return (l+r)%MOD;};
  auto g = [](int l, int r){return (l+r)%MOD;};
  auto h = [](int l, int r){return (l+r)%MOD;};
  auto p = [](int l, int r){return (l*r)%MOD;};
  segtree<int,int> seg(n, f, g, h, 0, 0, p);

  VI v(n);
  REP(i, n) v[hld.vid[i]] = s[i];
  seg.build(v);

  csum[0] = C[hld.inv[0]];
  FOR(i, 1, n) (csum[i] += csum[i-1] + C[hld.inv[i]]) %= MOD;

  int q;
  cin >> q;
  REP(i, q) {
    int type; cin >> type;
    if(type == 0) {
      int x, y, z;
      cin >> x >> y >> z; x--, y--;
      hld.for_each(x, y, [&](int l, int r){
        seg.update(l, r+1, z);
      });
    } else {
      int x, y;
      cin >> x >> y; x--, y--;
      int ans = 0;
      hld.for_each(x, y, [&](int l, int r){
        ans += seg.query(l, r+1);
      });
      cout << ans << endl;
    }
  }

  return 0;
}
0