結果

問題 No.235 めぐるはめぐる (5)
ユーザー polylogKpolylogK
提出日時 2019-09-11 12:00:39
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,186 ms / 10,000 ms
コード長 6,153 bytes
コンパイル時間 2,215 ms
コンパイル使用メモリ 192,804 KB
実行使用メモリ 39,168 KB
最終ジャッジ日時 2024-07-02 16:45:02
合計ジャッジ時間 7,996 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,186 ms
38,252 KB
testcase_01 AC 752 ms
39,168 KB
testcase_02 AC 1,075 ms
38,528 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

using namespace std;
template< typename Monoid, typename OperatorMonoid = Monoid >
struct LazySegmentTree
{
  using F = function< Monoid(Monoid, Monoid) >;
  using G = function< Monoid(OperatorMonoid, OperatorMonoid, int, int) >;
  using H = function< OperatorMonoid(Monoid, OperatorMonoid) >;

  int sz;
  vector< Monoid > data;
  vector< OperatorMonoid > lazy;
  const F f;
  const G g;
  const H h;
  const Monoid M1;
  const OperatorMonoid OM0;


  LazySegmentTree(int n, const F f, const G g, const H h,
                  const Monoid &M1, const OperatorMonoid OM0)
      : f(f), g(g), h(h), M1(M1), OM0(OM0)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    data.assign(2 * sz, M1);
    lazy.assign(2 * sz, OM0);
  }

  void set(int k, const Monoid &x)
  {
    data[k + sz] = x;
  }

  void build()
  {
    for(int k = sz - 1; k > 0; k--) {
      data[k] = f(data[2 * k + 0], data[2 * k + 1]);
    }
  }

  void propagate(int k, int l, int r)
  {
    if(lazy[k] != OM0) {
      if(k < sz) {
        lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]);
        lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
      }
      data[k] = g(data[k], lazy[k], l, r);
      lazy[k] = OM0;
    }
  }

  Monoid update(int a, int b, const OperatorMonoid &x, int k, int l, int r)
  {
    propagate(k, l, r);
    if(r <= a || b <= l) {
      return data[k];
    } else if(a <= l && r <= b) {
      lazy[k] = h(lazy[k], x);
      propagate(k, l, r);
      return data[k];
    } else {
      return data[k] = f(update(a, b, x, 2 * k + 0, l, (l + r) >> 1),
                         update(a, b, x, 2 * k + 1, (l + r) >> 1, r));
    }
  }

  Monoid update(int a, int b, const OperatorMonoid &x)
  {
    return update(a, b, x, 1, 0, sz);
  }


  Monoid query(int a, int b, int k, int l, int r)
  {
    propagate(k, l, r);
    if(r <= a || b <= l) {
      return M1;
    } else if(a <= l && r <= b) {
      return data[k];
    } else {
      return f(query(a, b, 2 * k + 0, l, (l + r) >> 1),
               query(a, b, 2 * k + 1, (l + r) >> 1, r));
    }
  }

  Monoid query(int a, int b)
  {
    return query(a, b, 1, 0, sz);
  }

  Monoid operator[](const int &k)
  {
    return query(k, k + 1);
  }
};

// build: you have to run it before you use
// for_each: process [l, r]
// for_each_edge: process [l, r]
// distance: returns the dist (l, r)
class heavy_light_decomposition {
	using size_type = size_t;

	using F = std::function<void (int, int)>;

	public:
	std::vector<std::vector<int>> g;
	std::vector<int> vid, inv;

	private:
	std::vector<int> head, sz, heavy, par, dep, type;

	void dfs(int root) {
		using P = std::pair<int, int>;
		
		par[root] = -1;
		dep[root] = 0;
		std::stack<P> st;
		st.push({root, 0});
		while(!st.empty()) {
			int v = st.top().first;
			int & i = st.top().second;
		
			if(i < g[v].size()) {
				int u = g[v][i++];
				if(u == par[v]) continue;
				par[u] = v;
				dep[u] = dep[v] + 1;
				st.push({u, 0});
			} else {
				st.pop();
				int tmp = 0;
				for(auto e: g[v]) {
					if(e == par[v]) continue;
					sz[v] += sz[e];
					if(tmp < sz[e]) {
						tmp = sz[e];
						heavy[v] = e;
					}
				}
			}
		}
	}
	void bfs(int root, int c, int & k) {
		std::queue<int> qu({root});
		while(!qu.empty()) {
			int h = qu.front(); qu.pop();

			for(int v = h; v != -1; v = heavy[v]) {
				type[v] = c;
				vid[v] = k++;
				inv[vid[v]] = v;
				head[v] = h;
				for(int e: g[v])
					if(e != par[v] and e != heavy[v]) qu.push(e);
			}
		}
	}

	public:
	heavy_light_decomposition() {}
	heavy_light_decomposition(int n) :
		g(n), vid(n, -1), head(n), sz(n, 1), heavy(n, -1),
		par(n), dep(n), inv(n), type(n) {}
	void add_edge(int a, int b) {
		g[a].push_back(b);
		g[b].push_back(a);
	}
	void build(std::vector<int> rs = std::vector<int>(1, 0)) {
		int c = 0, k = 0;
		for(int r: rs) {
			dfs(r);
			bfs(r, c++, k);
		}
	}
	int lca(int u, int v) {
		while(true) {
			if(vid[u] > vid[v]) std::swap(u, v);
			if(head[u] == head[v]) return u;
			v = par[head[v]];
		}
	}
	void for_each(int u, int v, const F & f) {
		while(true) {
			if(vid[u] > vid[v]) std::swap(u, v);
			f(std::max(vid[head[v]], vid[u]), vid[v]);
			if(head[u] != head[v]) v = par[head[v]];
			else break;
		}
	}
	void for_each_edge(int u, int v, const F & f) {
		while(true) {
			if(vid[u] > vid[v]) std::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 distance(int u, int v) {
		return dep[u] + dep[v] - 2 * dep[lca(u, v)];
	}
};

int main() {
	int n; scanf("%d", &n); std::vector<i64> s(n), c(n);
	for(int i = 0; i < n; i++) scanf("%d", &s[i]);
	for(int i = 0; i < n; i++) scanf("%d", &c[i]);

	heavy_light_decomposition hld(n);
	for(int i = 0; i < n - 1; i++) {
		int a, b; scanf("%d%d", &a, &b);

		hld.add_edge(a - 1, b - 1);
	}
	hld.build();

	std::vector<i64> S(n + 1);
	for(int i = 0; i < n; i++) S[i + 1] = S[i] + c[hld.inv[i]];

	const int MOD = 1e9 + 7;
	auto f = [MOD](i64 a, i64 b) { return (a + b) % MOD; };
	auto g = [MOD, S](i64 a, i64 b, int l, int r) {
		return ((S[r] - S[l]) % MOD * b % MOD + a) % MOD;
	};
	auto h = [MOD](i64 a, i64 b) { return (a + b) % MOD; };
	LazySegmentTree<i64> seg(n, f, g, h, 0, 0);
	for(int i = 0; i < n; i++) seg.set(i, s[hld.inv[i]]);
	seg.build();
	
	int q; scanf("%d", &q);
	while(q--) {
		int type; scanf("%d", &type);
		
		if(type == 0) {
			int x, y, z; scanf("%d%d%d", &x, &y, &z);

			auto f = [&seg, z](int l, int r) {
				seg.update(l, r + 1, z);
			};
			hld.for_each(x - 1, y - 1, f);
		} else {
			int x, y; scanf("%d%d", &x, &y);

			i64 ans = 0;
			auto f = [&seg, &ans, &MOD](int l, int r) {
				(ans += seg.query(l, r + 1)) %= MOD;
			};
			hld.for_each(x - 1, y - 1, f);
			printf("%lld\n", ans);
		}
	}
	return 0;
}
0