結果

問題 No.235 めぐるはめぐる (5)
ユーザー pekempeypekempey
提出日時 2015-09-06 11:48:51
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,393 ms / 10,000 ms
コード長 7,268 bytes
コンパイル時間 2,423 ms
コンパイル使用メモリ 186,500 KB
実行使用メモリ 108,020 KB
最終ジャッジ日時 2023-09-26 09:24:04
合計ジャッジ時間 8,774 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,393 ms
97,868 KB
testcase_01 AC 1,030 ms
108,020 KB
testcase_02 AC 1,306 ms
100,132 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, a) for (int i = 0; i < (a); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); i++)
#define repr(i, a) for (int i = (a) - 1; i >= 0; i--)
#define repr2(i, a, b) for (int i = (b) - 1; i >= (a); i--)
using namespace std;
typedef long long ll;

const int inf = 1e9;
const ll mod = 1e9 + 7;

template<class T>
struct RMQ {
	vector<T> seg;
	int size;
	T inf;
	RMQ(int n, T inf) {
		this->inf = inf;
		size = 1;
		while (size < n) size *= 2;
		seg.resize(size * 2 - 1, inf);
	}
	void update(int k, T x) {
		k += size - 1;
		seg[k] = x;
		while (k > 0) {
			k = (k - 1) / 2;
			seg[k] = min(seg[k * 2 + 1], seg[k * 2 + 2]);
		}
	}
	T query(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l) return inf;
		if (a <= l && r <= b) return seg[k];
		T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return min(vl, vr);
	}
	T query(int a, int b) {
		return query(a, b, 0, 0, size);
	}
};

struct LCA {
	RMQ<pair<int, int>> rmq;
	vector<pair<int, int> > euler;
	vector<vector<int> > G;
	vector<int> id;
	int root;
	LCA(int V) : rmq(V * 2 - 1, make_pair(inf, inf)), G(V), id(V), euler(V * 2 - 1) {}
	void add(int u, int v) {
		G[u].push_back(v);
		G[v].push_back(u);
	}
	void dfs(int curr, int prev, int depth, int &k) {
		id[curr] = k;
		euler[k++] = make_pair(depth, curr);
		for (int next : G[curr]) if (next != prev) {
			dfs(next, curr, depth + 1, k);
			euler[k++] = make_pair(depth, curr);
		}
	}
	void build(int root = 0) {
		this->root = root;
		int k = 0;
		dfs(root, -1, 0, k);
		rep (i, euler.size()) {
			rmq.update(i, euler[i]);
		}
	}
	int query(int u, int v) {
		return rmq.query(min(id[u], id[v]), max(id[u], id[v]) + 1).second;
	}
};

struct HL {
	vector<vector<int>> G, color, path;
	vector<int> parent, head, order, size, heads;
	int root;
	HL(int n) : G(n), color(n), parent(n), head(n), order(n), size(n), path(n) {}
	void add(int u, int v) {
		G[u].push_back(v);
		G[v].push_back(u);
	}
	int dfs(int curr, int prev) {
		int res = 1;
		parent[curr] = prev;
		rep (i, G[curr].size()) {
			int next = G[curr][i];
			if (next == prev) continue;
			int d = dfs(next, curr);
			color[curr][i] = d;
			res += d;
		}
		int maxi = max_element(color[curr].begin(), color[curr].end()) - color[curr].begin();
		rep (i, G[curr].size()) {
			color[curr][i] = maxi == i;
		}
		return res;
	}
	void dfs2(int curr, int prev) {
		rep (i, G[curr].size()) {
			int next = G[curr][i];
			if (next == prev) continue;
			if (color[curr][i]) {
				head[next] = head[curr];
				order[next] = order[curr] + 1;  
			}
			dfs2(next, curr);
		} 
	}
	void build(int root = 0) {
		this->root = root;
		int V = G.size();
		rep (i, V) color[i].resize(G[i].size());
		dfs(root, -1);
		rep (i, V) head[i] = i;
		dfs2(root, -1);
		rep (i, V) size[head[i]]++;
		rep (i, V) {
			if (i == head[i]) {
				heads.push_back(i);
				path[i].resize(size[i]);
			}
		}
		rep (i, V) {
			path[head[i]][order[i]] = i;
		}
	}
	int skip(int v) {
		return parent[head[v]];
	}
	int vid(int h, int ord) {
		return path[h][ord];
	}
};	

struct HLIterator {
	int u, v, l;
	HL *hl;
	LCA *lca;
	HLIterator(HL *hl, int u) : hl(hl), u(u), v(0), l(hl->root) {}
	HLIterator(HL *hl, LCA *lca, int u, int v) : hl(hl), lca(lca), u(u), v(v) {
		l = lca->query(u, v);
	}
	// head, [from, to)
	tuple<int, int, int> next() {
		if (hl->head[l] != hl->head[u]) {
			int pu = u;
			u = hl->skip(u);
			return make_tuple(hl->head[pu], 0, hl->order[pu] + 1);
		}
		if (hl->head[l] != hl->head[v]) {
			int pv = v;
			v = hl->skip(v);
			return make_tuple(hl->head[pv], 0, hl->order[pv] + 1);
		}
		int a = min(hl->order[u], hl->order[v]);
		int b = max(hl->order[u], hl->order[v]);
		u = -1; v = -1;
		return make_tuple(hl->head[l], a, b + 1);
	}
	bool has_next() {
		return u != -1 && v != -1;
	}
};

ll modulo(ll a) {
	a %= mod; a += mod; a %= mod;
	return a;
}

struct SegmentTree {
	vector<ll> seg, lazy, weight, wsum;
	int size;
	void init(int n) {
		size = 1;
		while (size < n) size *= 2;
		seg.resize(size * 2);
		lazy.resize(size * 2);
		weight.resize(size);
	}
	void set_value(int k, ll v) {
		seg[k + size - 1] = v;
	}
	void set_weight(int k, ll w) {
		weight[k] = w;
	}
	void build() {
		wsum.resize(size + 1);	
		rep (i, size) {
			wsum[i + 1] += wsum[i] + weight[i];
			wsum[i + 1] %= mod;
		}
		repr (i, size - 1) {
			seg[i] = seg[i * 2 + 1] + seg[i * 2 + 2];
			seg[i] %= mod;
		}
	}
	void evallazy(int k, int l, int r) {
		seg[k] += lazy[k] * (wsum[r] - wsum[l]);
		seg[k] = modulo(seg[k]);
		if (r - l > 1) {
			(lazy[k * 2 + 1] += lazy[k]) %= mod;
			(lazy[k * 2 + 2] += lazy[k]) %= mod;
		}
		lazy[k] = 0;
	}
	void update(int a, int b, ll v, int k, int l, int r) {
		evallazy(k, l, r);
		if (r <= a || b <= l) return;
		if (a <= l && r <= b) {
			lazy[k] = v;
			evallazy(k, l, r);
		} else {
			update(a, b, v, k * 2 + 1, l, (l + r) / 2);
			update(a, b, v, k * 2 + 2, (l + r) / 2, r);
			seg[k] = seg[k * 2 + 1] + seg[k * 2 + 2];
			seg[k] %= mod;
		}
	}
	void update(int a, int b, ll v) {
		update(a, b, v, 0, 0, size);
	}
	ll query(int a, int b, int k, int l, int r) {
		evallazy(k, l, r);
		if (r <= a || b <= l) return 0;
		if (a <= l && r <= b) return seg[k];
		ll res = 0;
		res += query(a, b, k * 2 + 1, l, (l + r) / 2);
		res += query(a, b, k * 2 + 2, (l + r) / 2, r);
		return res % mod;
	}
	ll query(int a, int b) {
		return query(a, b, 0, 0, size);
	}
};

SegmentTree seg[202020];

void update(HL &hl, LCA &lca, int x, int y, int z) {
	HLIterator it(&hl, &lca, x, y);
	while (it.has_next()) {
		auto t = it.next();
		int head = get<0>(t);
		int l = get<1>(t);
		int r = get<2>(t);
		seg[head].update(l, r, z);
	}
}

int query(HL &hl, LCA &lca, int x, int y) {
	HLIterator it(&hl, &lca, x, y);
	ll res = 0;
	while (it.has_next()) {
		auto t = it.next();
		int head = get<0>(t);
		int l = get<1>(t);
		int r = get<2>(t);
		res += seg[head].query(l, r);
		res %= mod;
	}
	return res;
}

struct Stopwatch {
	double begin;
	Stopwatch() {
		start();
	}
	void start() {
		begin = clock();
	}
	double elapsed() {
		double end = clock();
		double res = (double)(end - begin) / CLOCKS_PER_SEC * 1000.0;
		begin = end;
		return res;
	}
	void display(string text) {
		cerr << text << ":" << elapsed() << "ms" << endl;
	}
};

int main() {
	Stopwatch whole;
	int N;
	cin >> N;
	vector<int> S(N), C(N);
	rep (i, N) scanf("%d", &S[i]);
	rep (i, N) scanf("%d", &C[i]);
	HL hl(N);
	LCA lca(N);
	rep (i, N - 1) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		hl.add(a, b);
		lca.add(a, b);
	}
	Stopwatch sw;
	hl.build();
	sw.display("build HL");
	lca.build();
	sw.display("build LCA");
	for (int h : hl.heads) {
		seg[h].init(hl.size[h]);
	}
	sw.display("init SegmentTree");
	rep (i, N) {
		seg[hl.head[i]].set_value(hl.order[i], S[i]);
		seg[hl.head[i]].set_weight(hl.order[i], C[i]);
	}
	for (int h : hl.heads) {
		seg[h].build();	
	}
	sw.display("build SegmentTree");
	int Q;
	cin >> Q;
	while (Q--) {
		int q;
		scanf("%d", &q);
		if (q == 0) {
			int x, y, z;
			scanf("%d%d%d", &x, &y, &z);
			x--; y--;
			update(hl, lca, x, y, z);
		} else {
			int x, y;
			scanf("%d%d", &x, &y);
			x--; y--;
			ll ans = query(hl, lca, x, y);
			printf("%d\n", (int)ans);
		}
	}
	sw.display("query");
	whole.display("whole");
}
0