結果

問題 No.235 めぐるはめぐる (5)
ユーザー sune232002sune232002
提出日時 2015-06-26 23:35:58
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,428 ms / 10,000 ms
コード長 12,238 bytes
コンパイル時間 2,417 ms
コンパイル使用メモリ 192,440 KB
実行使用メモリ 60,260 KB
最終ジャッジ日時 2024-07-07 18:34:53
合計ジャッジ時間 8,371 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,428 ms
59,800 KB
testcase_01 AC 888 ms
60,260 KB
testcase_02 AC 1,301 ms
59,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REPR(i,n) for (int i=(int)(n)-1;i>=0;--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
#define tpl(...) make_tuple(__VA_ARGS__)
const int INF = 0x3f3f3f3f;
const double EPS = 1e-8;
const double PI = acos(-1);
const int dy[] = {-1,0,1,0};
const int dx[] = {0,1,0,-1};
typedef long long ll;
typedef pair<int,int> pii;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename Ch,typename Tr,typename C,typename=decltype(begin(C()))>basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>&os,
                                                                                                           const C& c){os<<'[';for(auto i=begin(c);i!=end(c);++i)os<<(i==begin(c)?"":" ")<<*i;return os<<']';}
template<class S,class T>ostream&operator<<(ostream &o,const pair<S,T>&t){return o<<'('<<t.first<<','<<t.second<<')';}
template<int N,class Tp>void output(ostream&,const Tp&){}
template<int N,class Tp,class,class ...Ts>void output(ostream &o,const Tp&t){if(N)o<<',';o<<get<N>(t);output<N+1,Tp,Ts...>(o,t);}
template<class ...Ts>ostream&operator<<(ostream&o,const tuple<Ts...>&t){o<<'(';output<0,tuple<Ts...>,Ts...>(o,t);return o<<')';}
template<class T>void output(T t,char z=10){if(t<0)t=-t,putchar(45);int c[20];
  int k=0;while(t)c[k++]=t%10,t/=10;for(k||(c[k++]=0);k;)putchar(c[--k]^48);putchar(z);}
template<class T>void outputs(T t){output(t);}
template<class S,class ...T>void outputs(S a,T...t){output(a,32);outputs(t...);}
template<class T>void output(T *a,int n){REP(i,n)cout<<a[i]<<(i!=n-1?',':'\n');}
template<class T>void output(T *a,int n,int m){REP(i,n)output(a[i],m);}
template<class T>bool input(T &t){int n=1,c;for(t=0;!isdigit(c=getchar())&&~c&&c-45;);
  if(!~c)return 0;for(c-45&&(n=0,t=c^48);isdigit(c=getchar());)t=10*t+c-48;t=n?-t:t;return 1;}
template<class S,class ...T>bool input(S&a,T&...t){input(a);return input(t...);}
template<class T>bool inputs(T *a, int n) { REP(i,n) if(!input(a[i])) return 0; return 1;}

#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)
#define tenll(x) ((ll)1e##x)

class LCA {
public:
  const vector<vector<int>>& e;
  int V, logV;
  vector<int> depth;
  vector<vector<int> > parent;

  LCA(const vector<vector<int>>& e) : e(e) {
    this->V = sz(e);
    logV = 0;
    while (V >= (1 << logV)) logV++;
    this->depth = vector<int>(V);
    this->parent = vector<vector<int> >(logV, vector<int>(V));

    dfs(0, -1, 0);
    build();
  }

  void dfs(int v, int par, int d) {
    depth[v] = d;
    parent[0][v] = par;
    for (auto to : e[v]) {
      if (par == to) continue;
      dfs(to, v, d + 1);
    }
  }

  void build() {
    for (int k = 0; k + 1 < logV; k++) {
      for (int v = 0; v < V; v++) {
        if (parent[k][v] < 0) parent[k + 1][v] = -1;
        else parent[k + 1][v] = parent[k][parent[k][v]];
      }
    }
  }

  int query(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    for (int k = 0; k < logV; k++) {
      if ((depth[v] - depth[u]) >> k & 1)
        v = parent[k][v];
    }
    if (u == v) return u;

    for (int k = logV - 1; k >= 0; k--) {
      if (parent[k][u] != parent[k][v]) {
        u = parent[k][u];
        v = parent[k][v];
      }
    }
    return parent[0][u];
  }
};

template<int MOD>
struct ModInt {
  int x;
  ModInt() : x(0) {}
  ModInt(ll s) { if ((x = s % MOD) < 0) x += MOD; }
  ModInt operator+=(ModInt rhs) { if ((x+=rhs.x) >= MOD) x -= MOD; return *this; }
  ModInt operator-=(ModInt rhs) { if ((x-=rhs.x) < 0) x += MOD; return *this; }
  ModInt operator*=(ModInt rhs) { x = (ll)x*rhs.x % MOD; return *this; }
  ModInt operator+(ModInt rhs) const { return ModInt(*this) += rhs; }
  ModInt operator-(ModInt rhs) const { return ModInt(*this) -= rhs; }
  ModInt operator*(ModInt rhs) const { return ModInt(*this) *= rhs; }
  ModInt operator/=(ModInt rhs) {
    static const ll inv2 = ModInt(2).inv().x; // 2で割るのは特別に保存してみる
    ll i = (rhs.x == 2 ? inv2 : rhs.inv().x);
    x = x*i%MOD; return *this;
  }
  ModInt operator/(ModInt rhs) const { return ModInt(*this) /= rhs; }
  ModInt inv() { return pow(MOD-2); }
  ModInt pow(ll n) const {
    ModInt r = 1, t = x;
    for (;n;n>>=1,t*=t) if (n&1) r *= t;
    return r;
  }
  static ModInt strnum(const string &n) {ModInt a = 0; for (char c:n) a = a*10+c-'0'; return a;}
  friend ostream& operator<<(ostream &os, const ModInt rhs){ return os << rhs.x; }
};
typedef ModInt<int(1e9+7)> mint;

struct Data {
  mint csum;
  mint val;
  void init(int l, int s, int c) {     // 末端ノードの初期化
    val = s;
    csum = c;
  }
  void change(mint v) { // ノードの値を変える
    val += v;
  }
  void combine(const Data &l, const Data &r) { // 区間の統合
    val = l.val + r.val;
    csum = l.csum + r.csum;
  }
  string str() {
    stringstream ss;
    ss << val;
    return ss.str();
  }
};

struct Param {
  mint z;
  Param() {init();}
  void init() {
    z = 0;
  }
  void update(const Param &pp) {
    // pp : 親のParam
    // 今のthisにさらにppが適用された場合にthisがどうなるか
    z += pp.z;
  }
  void update(int _z, int l, int r) {
    z += _z;
  }
  void apply(Data &d, int l, int r) const {
    // 区間に関するクエリに答えなければならないときは
    // ここの適用を効率的にできるかが鍵
    mint v = d.csum * z;
    d.change(v);
  }
};

struct SegTree {
  int l,r;                      // 区間の範囲
  int mid;
  SegTree *cl, *cr;
  Param param;
  Data d;
  SegTree(int l, int r, const vector<int> &s, const vector<int> &c) : l(l), r(r) {
    mid = (l+r)>>1;
    if (l+1 == r) {
      d.init(l,s[l],c[l]);
    } else {
      cl = new SegTree(l,mid,s,c);
      cr = new SegTree(mid,r,s,c);
      d.combine(cl->d,cr->d);
    }
  }
  void change(int k, int v) {
    if (l+1 == r) {
      d.change(v);
    } else {
      down();
      if (k < mid) cl->change(k,v);
      else cr->change(k,v);
      d.combine(cl->d,cr->d);
    }
  }
  Data query(int L, int R) {
    if (L<=l && r<=R) return d;
    down();
    if (R<=mid) return cl->query(L,R);
    if (L>=mid) return cr->query(L,R);
    Data res;
    res.combine(cl->query(L,R), cr->query(L,R));
    return res;
  }
  void down() {
    cl->update(param);
    cr->update(param);
    cl->param.update(param);
    cr->param.update(param);
    param.init();
  }

  void update(const Param &par) {
    par.apply(d, l, r);
  }

  void apply(int L, int R, int z) {
    if (L<=l && r<=R) {
      param.update(z,L,R);
      // ここでは今回分のみ自分に適用する必要がある．
      Param par;
      par.update(z,L,R);
      par.apply(d,l,r);
      return;
    }
    down();
    if (L<mid) cl->apply(L,R,z);
    if (R>mid) cr->apply(L,R,z);
    d.combine(cl->d,cr->d);
  }
  void print(bool f = 1) {
    if (l+1 == r) {
      cout << d.str() << " ";
      return;
    }
    down();
    cl->print(0);
    cr->print(0);
    if (f) cout << endl;
  }
};

class RangeTree {
public:
  int n;
  vector<vector<int>> dat;
  RangeTree(vector<int>& a) {
    n = 1;
    while (n < sz(a)) n <<= 1;
    dat.resize(2 * n - 1);
    REP(i, n) {
      int k = n - 1 + i;
      if (i < sz(a)) dat[k].push_back(a[i]);
      else dat[k].push_back(ten(8));
    }
    for (int i = n - 2; i >= 0; i--) {
      dat[i].resize(sz(dat[2 * i + 1]) + sz(dat[2 * i + 2]));
      merge(dat[2 * i + 1].begin(), dat[2 * i + 1].end(), dat[2 * i + 2].begin(), dat[2 * i + 2].end(), dat[i].begin());
    }
  }
  int query(int l, int r, int val) {
    return query(l, r, val, 0, 0, n);
  }
  int query(int l, int r, int val, int k, int a, int b) {
    if (r <= a || b <= l) return 0;
    if (l <= a && b <= r) {
      return lower_bound(dat[k].begin(), dat[k].end(), val + 1) - dat[k].begin();
    }
    return query(l, r, val, 2 * k + 1, a, (a + b) / 2) + query(l, r, val, 2 * k + 2, (a + b) / 2, b);
  }
};

//heavy-light decomposition
class HL_decomposition {
public:
  const vector<vector<int>>& e;
  const int n;
  vector<int> par, depth, ord; //親,深さ、トポロジカルソート
  vector<int> cluster; //decompositionした結果どのクラスタに属するか
  vector<vector<int> > pathes; //各クラスタの、上から下へのパス
  vector<int> path_idx; // path_idx[v] = 上記パスでのindex

  void init(int v) {
    depth.resize(n, 0);
    par.resize(n, 0);
    ord.resize(n, 0);

    depth[v] = 0;
    par[v] = -1;
    ord[0] = v; //ordをキューとして使い、bfsする
    for (int p = 0, r = 1; p < r; p++) {
      int cur = ord[p];
      for (int nv : e[cur]) {
        if (nv == par[cur]) continue;
        ord[r++] = nv;
        par[nv] = cur;
        depth[nv] = depth[cur] + 1;
      }
    }
  }

  void decomposition() {
    vector<int> subtree_size(n, 1);
    for (int i = n - 1; i > 0; i--) subtree_size[par[ord[i]]] += subtree_size[ord[i]];
    cluster.resize(n, -1);
    int cluster_type = 0;
    REP(i, n) {
      int u = ord[i];
      if (cluster[u] == -1) cluster[u] = cluster_type++;
      int max_subsize = -1, selected = -1;
      for (int v : e[u]) {
        if (par[u] != v && max_subsize < subtree_size[v]) {
          max_subsize = subtree_size[v];
          selected = v;
        }
      }
      if (selected != -1) cluster[selected] = cluster[u];
    }
  }

  void enum_pathes() {
    int cluster_num = 0;
    vector<int> rp(n);
    REP(i, n) {
      rp[cluster[i]]++;
      cluster_num = max(cluster_num, cluster[i]);
    }
    cluster_num++;
    pathes.resize(cluster_num);
    REP(i, cluster_num) pathes[i].resize(rp[i]);
    for (int i = n - 1; i >= 0; i--) {
      int u = ord[i];
      pathes[cluster[u]][--rp[cluster[u]]] = u;
    }
  }

  void set_path_idx() {
    path_idx.resize(n);
    for (const vector<int>& path : pathes) {
      REP(i, sz(path)) path_idx[path[i]] = i;
    }
  }

public:
  HL_decomposition(const vector<vector<int>>& e) : e(e), n(sz(e)) {
    init(0);
    decomposition();
    enum_pathes();
    set_path_idx();
  }
};

// exsample of how to use
class tree_query {
  LCA* lca;
  HL_decomposition *hl;
  vector<SegTree*> rts;
  int mx;
public:
  tree_query(vector<vector<int>>& e, vector<int>& s, vector<int>& c) {
    lca = new LCA(e);
    hl = new HL_decomposition(e);
    rts.resize(sz(hl->pathes));
    REP(i, sz(rts)) {
      vector<int> cs, ss;
      for (int v : hl->pathes[i]) {
        ss.push_back(s[v]);
        cs.push_back(c[v]);
      }
      rts[i] = new SegTree(0, cs.size(), ss, cs);
    }
  }

  void update(int v, int z) {
    while (v != -1) {
      rts[hl->cluster[v]]->apply(0, hl->path_idx[v] + 1, z);
      v = hl->par[hl->pathes[hl->cluster[v]][0]];
    }
  }

  void update(int u, int v, int z) {
    int p = lca->query(u, v);
    update(u,z);
    update(v,z);
    update(p,-z);
    if (lca->parent[0][p] != -1)
      update(lca->parent[0][p],-z);
  }

  mint count(int v) {
    mint ret = 0;
    while (v != -1) {
      ret += rts[hl->cluster[v]]->query(0, hl->path_idx[v] + 1).val;
      v = hl->par[hl->pathes[hl->cluster[v]][0]];
    }
    return ret;
  }

  mint query(int u, int v) {
    int p = lca->query(u, v);
    mint a1 = count(u);
    mint a2 = count(v);
    mint a3 = count(p);
    mint a4 = lca->parent[0][p] != -1 ? count(lca->parent[0][p]) : 0;
    mint cnt = a1 + a2 - a3 - a4;
    return cnt;
  }

  ~tree_query() {
    delete lca;
    delete hl;
    REP(i, sz(rts)) delete rts[i];
  }
};

int main() {
  int n; cin >> n;
  vector<int> s(n), c(n);
  vector<vector<int>> e(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--;
    e[a].push_back(b);
    e[b].push_back(a);
  }
  tree_query tq(e, s, c);
  int q;
  cin >> q;
  REP(i, q) {
    int t;
    input(t);
    if (t == 0) {
      int x, y, z;
      input(x,y,z);
      x--;y--;
      tq.update(x, y, z);
    } else {
      int x, y;
      input(x,y);
      x--;y--;
      mint res = tq.query(x, y);
      output(res.x);
    }
  }
}
0