結果

問題 No.235 めぐるはめぐる (5)
ユーザー pekempeypekempey
提出日時 2016-10-05 06:24:57
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,064 ms / 10,000 ms
コード長 3,575 bytes
コンパイル時間 2,474 ms
コンパイル使用メモリ 186,864 KB
実行使用メモリ 25,660 KB
最終ジャッジ日時 2024-05-01 12:42:43
合計ジャッジ時間 7,014 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,064 ms
24,848 KB
testcase_01 AC 668 ms
25,660 KB
testcase_02 AC 963 ms
24,836 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int in()’:
main.cpp:126:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  126 |         scanf("%d", &t);
      |         ~~~~~^~~~~~~~~~

ソースコード

diff # 

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
uint32_t inv;
int r2;

int reduce(uint64_t x) {
	uint64_t y = uint64_t(uint32_t(x) * inv) * mod;
	return int(x >> 32) + mod - int(y >> 32);
}

int transform(int n) {
	return reduce(int64_t(n) * r2);
}

int normalize(int n) {
	return n >= mod ? n - mod : n;
}

void init_montgomery_reduction() {
	inv = 1;
	for (int i = 0; i < 5; ++i) inv *= 2 - inv * uint32_t(mod);
	r2 = -uint64_t(mod) % mod;
}

void chadd(int &a, int b) {
	(a += b - mod) < 0 ? a += mod : a;
}

int modadd(int a, int b) {
	return (a += b - mod) < 0 ? a + mod : a;
}

int modmul(int a, int b) {
	return reduce(int64_t(a) * b);
}

struct HLDecomposition {
	vector<vector<int>> g;
	vector<int> vid, head, heavy, parent;

	HLDecomposition(int n) : g(n), vid(n, -1), head(n), heavy(n, -1), parent(n) {}

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

	void build() {
		dfs(0, -1);
		bfs();
	}

	int dfs(int curr, int prev) {
		parent[curr] = prev;
		int sub = 1, max_sub = 0;
		for (int next : g[curr]) if (next != prev) {
			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++;
				head[i] = h;
				for (int j : g[i]) if (j != parent[i] && j != heavy[i]) q.push(j);
			}
		}
	}

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

const int N = 1 << 18;
int coeff[N * 2], sum[N * 2], add[N * 2];

void push(int k) {
	if (add[k] == 0) return;
	chadd(sum[k], modmul(coeff[k], add[k]));
	if (k < N) {
		chadd(add[k * 2 + 0], add[k]);
		chadd(add[k * 2 + 1], add[k]);
	}
	add[k] = 0;
}

void update(int a, int b, int v, int k = 1, int l = 0, int r = N) {
	push(k);
	if (r <= a || b <= l) return;
	if (a <= l && r <= b) {
		chadd(add[k], v);
		push(k);
		return;
	}
	update(a, b, v, k * 2 + 0, l, (l + r) / 2);
	update(a, b, v, k * 2 + 1, (l + r) / 2, r);
	sum[k] = modadd(sum[k * 2 + 0], sum[k * 2 + 1]);
}

int query(int a, int b, int k = 1, int l = 0, int r = N) {
	if (r <= a || b <= l) return 0;
	push(k);
	if (a <= l && r <= b) return sum[k];
	int L = query(a, b, k * 2 + 0, l, (l + r) / 2);
	int R = query(a, b, k * 2 + 1, (l + r) / 2, r);
	return modadd(L, R);
}

int in() {
	int t;
	scanf("%d", &t);
	return t;
}

int in_t() {
	return transform(in());
}

int main() {
	init_montgomery_reduction();

	int n = in();

	vector<int> S(n), C(n);
	for (int i = 0; i < n; i++) S[i] = in_t();
	for (int i = 0; i < n; i++) C[i] = in_t();

	HLDecomposition hld(n);
	for (int i = 1; i < n; i++) hld.add(in() - 1, in() - 1);
	hld.build();

	for (int i = 0; i < n; i++) {
		sum[hld.vid[i] + N] = S[i];
		coeff[hld.vid[i] + N] = C[i];
	}
	for (int i = N - 1; i >= 1; i--) {
		sum[i] = modadd(sum[i * 2 + 0], sum[i * 2 + 1]);
		coeff[i] = modadd(coeff[i * 2 + 0], coeff[i * 2 + 1]);
	}

	int q = in();
	while (q--) {
		int t = in();

		if (t == 0) {
			int u = in() - 1, v = in() - 1, z = in_t();
			hld.for_each(u, v, [&](int l, int r) {
				update(l, r + 1, z);
			});
		} else {
			int u = in() - 1, v = in() - 1;
			int ans = 0;
			hld.for_each(u, v, [&](int l, int r) {
				chadd(ans, query(l, r + 1));
			});
			printf("%d\n", normalize(reduce(ans)));
		}
	}
}
0