結果

問題 No.235 めぐるはめぐる (5)
ユーザー okadukiokaduki
提出日時 2017-11-05 22:57:42
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 934 ms / 10,000 ms
コード長 6,551 bytes
コンパイル時間 2,258 ms
コンパイル使用メモリ 185,260 KB
実行使用メモリ 51,428 KB
最終ジャッジ日時 2023-08-15 18:46:37
合計ジャッジ時間 6,699 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 934 ms
44,864 KB
testcase_01 AC 607 ms
51,428 KB
testcase_02 AC 794 ms
45,772 KB
権限があれば一括ダウンロードができます

ソースコード

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;
}
0