結果

問題 No.235 めぐるはめぐる (5)
コンテスト
ユーザー kazuma
提出日時 2017-06-25 05:07:23
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,825 ms / 10,000 ms
コード長 4,028 bytes
コンパイル時間 2,268 ms
コンパイル使用メモリ 186,132 KB
実行使用メモリ 38,660 KB
最終ジャッジ日時 2024-10-04 08:18:35
合計ジャッジ時間 10,129 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;

class HLDecomposition {
	vector<vector<int>> g;
	vector<int> vid, head, heavy, parent, depth;
public:
	vector<int> inv;
private:
	int dfs(int curr, int prev) {
		parent[curr] = prev;
		int sub = 1, max_sub = 0;
		for (int next : g[curr]) if (next != prev) {
			depth[next] = depth[curr] + 1;
			int sub_next = dfs(next, curr);
			sub += sub_next;
			if (max_sub < sub_next) max_sub = sub_next, heavy[curr] = next;
		}
		return sub;
	}
	void bfs() {
		int k = 0;
		queue<int> q({ 0 });
		while (!q.empty()) {
			int h = q.front(); q.pop();
			for (int i = h; i != -1; i = heavy[i]) {
				vid[i] = k++;
				inv[vid[i]] = i;
				head[i] = h;
				for (int j : g[i]) if (j != parent[i] && j != heavy[i]) q.push(j);
			}
		}
	}
public:
	HLDecomposition(int n)
		: g(n), vid(n, -1), head(n), heavy(n, -1), parent(n), depth(n), inv(n) {}

	void add(int u, int v) {
		g[u].push_back(v);
		g[v].push_back(u);
	}
	void build() {
		dfs(0, -1);
		bfs();
	}
	void for_each(int u, int v, function<void(int, int)> f) {
		if (vid[u] > vid[v]) swap(u, v);
		f(max(vid[head[v]], vid[u]), vid[v]);
		if (head[u] != head[v]) for_each(u, parent[head[v]], f);
	}
};

class LazySegmentTree {
	const int n;
	const ll id;
	vector<ll> data, data2, C;
	int size(int n) {
		int res = 1;
		while (res < n) res <<= 1;
		return res;
	}
	ll sub(int l, int r, int node, int lb, int ub) {
		if (ub <= l || r <= lb) return id;
		if (l <= lb && ub <= r) {
			return data2[node] == id ? data[node] : (data[node] + data2[node] * C[node] % mod) % mod;
		}
		int left = node * 2, right = node * 2 + 1;
		if (data2[node] != id) {
			data2[left] = (data2[left] + data2[node]) % mod;
			data2[right] = (data2[right] + data2[node]) % mod;
			data[node] = (data[node] + data2[node] * C[node] % mod) % mod;
			data2[node] = id;
		}
		return (sub(l, r, left, lb, (lb + ub) / 2) + sub(l, r, right, (lb + ub) / 2, ub)) % mod;
	}
	void suc(int l, int r, int node, int lb, int ub, ll val) {
		if (ub <= l || r <= lb) return;
		if (l <= lb && ub <= r) {
			data2[node] = (data2[node] + val) % mod;
			return;
		}
		int left = node * 2, right = node * 2 + 1;
		if (data2[node] != id) {
			data2[left] = (data2[left] + data2[node]) % mod;
			data2[right] = (data2[right] + data2[node]) % mod;
			data[node] = (data[node] + data2[node] * C[node] % mod) % mod;
			data2[node] = id;
		}
		suc(l, r, left, lb, (lb + ub) / 2, val);
		suc(l, r, right, (lb + ub) / 2, ub, val);
		data[node] = ((data[left] + data2[left] * C[left] % mod) % mod + (data[right] + data2[right] * C[right] % mod) % mod) % mod;
	}
public:
	LazySegmentTree(const vector<ll>& v_, const vector<ll>& C_) :
		n(size(v_.size())), id(0), data(n * 2, id), data2(n * 2, id), C(n * 2, id) {
		for (int i = 0; i < (int)v_.size(); i++) {
			data[i + n] = v_[i] % mod;
		}
		for (int i = n - 1; i > 0; i--) {
			data[i] = (data[i * 2] + data[i * 2 + 1]) % mod;
		}
		for (int i = 0; i < (int)C_.size(); i++) {
			C[i + n] = C_[i] % mod;
		}
		for (int i = n - 1; i > 0; i--) {
			C[i] = (C[i * 2] + C[i * 2 + 1]) % mod;
		}
	}
	void add(int l, int r, ll val) {
		suc(l, r + 1, 1, 0, n, val);
	}
	ll getSum(int l, int r) {
		return sub(l, r + 1, 1, 0, n);
	}
};

int main()
{
	ll N, Q, com, X, Y, Z;
	cin >> N;
	vector<ll> S(N), C(N), bs(N), bc(N);
	for (int i = 0; i < N; i++) {
		cin >> S[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> C[i];
	}
	HLDecomposition hl(N);
	for (int i = 0, u, v; i < N - 1; i++) {
		cin >> u >> v; u--; v--;
		hl.add(u, v);
	}
	hl.build();
	for (int i = 0; i < N; i++) {
		bs[i] = S[hl.inv[i]];
		bc[i] = C[hl.inv[i]];
	}
	LazySegmentTree lst(bs, bc);
	cin >> Q;
	while (Q--) {
		cin >> com;
		if (com) {
			cin >> X >> Y; X--; Y--;
			ll res = 0;
			hl.for_each(X, Y, [&](int l, int r) {
				res = (res + lst.getSum(l, r)) % mod;
			});
			printf("%d\n", (int)res);
		}
		else {
			cin >> X >> Y >> Z; X--; Y--;
			hl.for_each(X, Y, [&](int l, int r) {
				lst.add(l, r, Z);
			});
		}
	}
	return 0;
}
0